(11C) Prime or Not Prime Number
01-20-2018, 01:04 PM (This post was last modified: 01-25-2018 09:33 AM by Gamo.)
Post: #1
 Gamo Senior Member Posts: 623 Joined: Dec 2016
(11C) Prime or Not Prime Number
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
01-20-2018, 06:17 PM (This post was last modified: 01-20-2018 06:43 PM by Dieter.)
Post: #2
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (11C) Prime or Not Prime Number
(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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)