(11C) Prime or Not Prime Number

[Gamo]

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

Code:


LBL A
STO 1
SQRT
INT
STO 2
1
X=Y? (TEST 5)
RTN
LBL 1
RCL 1
RCL 2
/
FRAC
X=0?
RTN
1
RCL 2
1
-
STO 2
X>Y? (TEST 7)
GTO 1
RTN
R/S

Here is another program to develop the Next Number of Prime.

Code:


LBL B
2
÷
INT
2
x
1
+
STO 0
LBL 5
3
STO 1
LBL 4
RCL 0
RCL 1
÷
LSTx
X>Y (TEST 7)
GTO 0
X<>Y
INT
LSTx
X=Y (TEST 5)
GTO 3
2
STO+1
GTO 4
LBL 0
RCL 0
R/S
LBL 3
2
STO+0
GTO5

Example: if the start number is prime the same starting number repeated.

Start 110 B > 113 > Repeat R/S > 127, 131, 137, 139,....

Start 13 B > 13 > Repeat R/S > 17, 19, 23, 29,.....

Large number will compute faster with the modern 15C

Try this number 899,880,277 to start.
Repeat R/S for next prime is 899,880,281 in 2 second using HP-15C Emulator on PC.

Gamo

[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