(11C) Prime or Not Prime Number

[Dieter]

(01-20-2018 01:04 PM)Gamo Wrote:  This program check to see if the number is Prime or not Prime number.
Result 0 is Not Prime Number
Result 1 is Prime Numer

Your program divides the input n by every divisor from int(sqrt(n)) down to 2. Why don't you simply use DSE then?

Code:

LBL A
STO 1
SQRT
INT
EEX
CHS
3
+
STO I
LBL 1
RCL 1
RCL I
INT
/
FRAC
X=0?
RTN
DSE
GTO 1
1
RTN

But this method is not very efficient as it also checks all even divisors. These could be sorted out. Also testing the divisors in ascending order usually is much faster. For numbers up to 1 000 000 you can use ISG which is faster than a manually controlled loop:

Code:

LBL A
STO 1
2
/         // first check if n is even
FRAC
X=0?
RTN
RCL 1
SQRT
INT
,
0
2
+
EEX
3
/
3
+
STO I     // loop control number = 3,ddd02 where ddd is the max. divisor
LBL 1
RCL 1
RCL I
/
FRAC
X=0?
RTN
ISG
GTO 1
1
RTN

For n > 1 000 000 a manually controlled loop is required:

Code:

LBL A
STO 1
2
STO 2
/         // first check if n is even
FRAC
X=0?
GTO 3
3
STO 2
LBL 1
RCL 1
RCL 2
/
LstX
X>Y?      // check if d > n/d, i.e. d > sqrt(n)
GTO 2
R↓
FRAC
X=0?
GTO 3
2
STO+2
GTO 1
LBL 2
1
STO 2
LBL 3
RCL 2
RTN

This version returns the smallest divisor of n. If this is 1, n is prime. ;-)

Example:
13573  f [A] => 7   n is divisible by 7
13577  f [A] => 1   n is prime

Dieter