(12C) Check if given number is Prime Number or not

[Dieter]

(09-10-2018 04:16 PM)Joe Horn Wrote:  Unless I'm mistaken, for an input of X, you're testing all numbers 2 through X.

Almost. It's 2 to X–1 (since X is always divisible by X).

(09-10-2018 04:16 PM)Joe Horn Wrote:  But you only need to check 2 through the INTG of the square root of X. This would make the program finish much faster for primes. For example, for an input of 101, you can stop checking at 10 instead of going all the way up to 101.

You can also check whether the input is even (=> no prime) and then only test the odd divisors. For the 101 example this means that not 99 divisors have to be checked but only five: 2, 3, 5, 7 and 9 (as 11 already is > √101). That's a speedup by a factor of almost 20.

It could be done this way:

Code:

01 STO 0
02 √x
03 STO 1
04 RCL 0
05 2
06 STO 2
07 ÷
08 FRAC
09 X=0?
10 GTO 29
11 3
12 STO 2
13 RCL 1
14 RCL 2
15 X≤Y?
16 GTO 20
17 RCL 0
18 1
19 GTO 00
20 RCL 0
21 RCL 2
22 ÷
23 FRAC
24 X=0?
25 GTO 29
26 2
27 STO+2
28 GTO 13
29 RCL 2
30 0
31 GTO 00

Enter an integer > 2 (smaller values will not work) and get a 1 (input is prime) or 0 (not prime). In this case [X⇄Y] shows the smallest divisor.

199 [R/S] => 1
So 199 is prime

899 [R/S] => 0   [X⇄Y] => 29
So 899 is not prime, it can be divided by 29.

Dieter