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

[Thomas Klemm]

This works only for odd numbers. (Cf. Fermat's factorization method)

Code:

01 STO 0   ; N
02 √x      ; √N
03 INTG    ; ⌊√N⌋
04 STO 1   ; a = ⌊√N⌋
05 1       ; 1
06 STO+ 1  ; a ← a+1
07 RCL 1   ; a
08 ENTER   ; a     a
09 ×       ; a²
10 RCL 0   ; N
11 -       : b²=a²-N
12 √x      ; b
13 FRAC    ; {b}
14 x=0     ; is b a square ?
15 GTO 17  ; factors found
16 GTO 05  ; next try
17 RCL 1   ; a
18 LSTx    ; b     a
19 +       ; a+b
20 RCL 1   ; a     a+b
21 LSTx    ; b     a       a+b
22 -       ; a-b   a+b

Examples

899
R/S
29
x<>y
31

199
R/S
1
x<>y
199 (is prime)

1,403
R/S
23
x<>y
61

5,959
R/S
59
x<>y
101

99,799,811
R/S
9,973
x<>y
10,007

Cheers
Thomas