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

[Gamo]

Program to check if the given number is Prime Number or Not.

1 Display is Yes this is a prime number
0 Display is No this is not a prime number

Procedure: n [R/S] display 0 or 1 [X<>Y] your given number

Example:

199 [R/S] display 1 // Yes this is a prime number
[X<>Y] display 199

153 [R/S] display 0 // No this is not a prime number
[X<>Y] display 153

Program:

Code:


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

Remark:
The larger the number the longer time it takes to give result even on HP-12C+
when the display show "running" and keep going that always is a prime number since
the result when it is not a prime number will show 0 instantly.

On the HP-12C emulator this program run extremely fast.

Gamo

[Joe Horn]

Unless I'm mistaken, for an input of X, you're testing all numbers 2 through X. 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.

[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

[Albert Chan]

What happens if no calculator ?
From book "Dead Reckoning: Calculating without Instrument", Fermat have a way that required no divisions !

Assume N is odd, the trick is start from the middle, integer X slightly bigger than sqrt(N):
If N had any factors, it must be in the form N = (X - Y)(X + Y) = X^2 - Y^2, X > Y
Rearrange, we get Y^2 = X^2 - N

The problem now is to recognize valid Y^2: last 2 digits must be 00, e1, e4, 25, d6, e9
Another validity check: Y^2 % 9 must be 0, 1, 4, 7

If N is prime, when to stop the search ? Let P be minimum prime to be tested:

X - Y = X - sqrt(X^2 - N) >= P
X - P >= sqrt(X^2 - N)
X^2 - 2P X + P^2 >= X^2 - N
N + P^2 >= 2P X
X <= (N/P + P) / 2

If X increase by 1, Y^2 increase by (X + 1)^2 - X^2 = 2 X + 1

Try N = 199, slightly below 15^2 = 225
N%9=1, N%5=4, thus P=7
X <= (199/7 + 7)/2 < (29+7)/2 = 18, thus X <= 17
X : Y^2
15 225-199 = 26
16 +31 => 57,
17 +33 => 90, STOP, N is Prime

Try N = 1403, 40^2=1600, 39^2=1600-79=1521, 38^2=1521-77=1444
N%9=8, N%5=3, N%7=3, thus P=11
X <= (1403/11 + 11)/2 < (128+11)/2 = 69.5, thus X <= 69
X : Y^2
38 1444-1403 = 41
39 +77 => 118
40 +79 => 197
41 +81 => 278
42 +83 => 361 = 19^2, thus 1403 = (42-19)(42+19) = 23*61, a composite

[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

[Gamo]

I have try program from Dieter version and this one run much faster very nice program.

With this program I test one prime number to real HP-12C, Emulator for 12C and 12C Platinum

The prime number is 9,000,000,001

Result on:

Real 12C answer 0 [X<>Y] 2

Emulator 12C answer 0 [X<>Y] 2

Emulator 12C Platinum 1 X<>Y 9,000,000,001

Is this another rounding problem on the 12C ?

Thank You

Gamo

[Thomas Klemm]

(09-11-2018 05:42 AM)Gamo Wrote:  Is this another rounding problem on the 12C ?

Yes. Since the real HP-12C uses 10 digits: 9,000,000,001 ÷ 2 = 4,500,000,001.
The fractional part of this number is 0 and the program jumps to line 29:

Code:

04 RCL 0
05 2
06 STO 2
07 ÷
08 FRAC
09 X=0?
10 GTO 29

And thus the program tells you erroneously that this number is divisible by 2.

HTH
Thomas

[Dieter]

(09-11-2018 05:42 AM)Gamo Wrote:  The prime number is 9,000,000,001

Result on:

Real 12C answer 0 [X<>Y] 2

Emulator 12C answer 0 [X<>Y] 2

Emulator 12C Platinum 1 X<>Y 9,000,000,001

Is this another rounding problem on the 12C ?

As Thomas already pointed out, the problem is the 12C's 10-digit precision. Here 9.000.000.001 divided by 2 simply is 4.500.000.001 – an integer, so the program thinks that the input is divisible by 2 and thus not a prime. The same would also happen when dividing by 3, 5, 7 or 9 and even 25.

As already discussed in the other thread with the program that checks whether one integer is a power of another, the 12CP does not seem to round its results to 10 significant digits. Which means that here a fractional part exists and thus the test performs correctly.

But this seems to be a bug in the 12CP emulator. I don't know much about the physical 12CP. How does it work? Does it have the same 10-digit precision as the 12C? Or does it use a higher precision while only 10 (out of 12 or 15) digits are displayed?

You may try this: calculate 4.444.444.444 / 3 and get 1.481.481.481. Now subtract 1.481.481.481 (or press g FRAC). On a real 12C the result is 0. But what do you get on the 12CP emulator? 0,3? 0,333? Please post all digits (i.e. as displayed in FIX 9).

Having said that, the largest input for a number to test is 1.999.999.999.
So the largest prime is 1.999.999.973. How long does this take on your various devices?

Dieter

[Gamo]

Just check the spec sheet on HP-12C Platinum
Internal Precision is 15 digits.

The 12C internal precision is 12 digits.

Test 1.999.999.973 prime number

Result on:

Emulator both 12C and 12C Platinum
Display 1 and speed took about 1 second

Real Hp-12C+ (not original edition)
Display 1 and speed took about 2 minutes


Gamo

[Dieter]

(09-11-2018 08:03 AM)Gamo Wrote:  Just check the spec sheet on HP-12C Platinum
Internal Precision is 15 digits.

The 12C internal precision is 12 digits.

Sure? Not 13?

But the essential point here is not the internal precision but what is returned to the user. Do the 12C Platinum or 12C+ (real hardware) return 10 or 12 digits? In both cases the display has 10 digits. What do you see after 3 [1/x] 30 [x] in FIX 9 mode? 10,00000000 or 9,999999999 ?

Also, could you or someone else please do the following test on a hardware 12C Platinum or 12C+? As already mentioned in my previous post:

Quote:You may try this: calculate 4.444.444.444 / 3 and get 1.481.481.481. Now subtract 1.481.481.481 (or press g FRAC). On a real 12C the result is 0. But what do you get on the 12CP emulator? 0,3? 0,333? Please post all digits (i.e. as displayed in FIX 9).

I really would like to know what results are produced both by the real (hardware) calculators as well as the emulators (please state which one).

Dieter

[rprosperi]

(09-13-2018 06:35 PM)Dieter Wrote:  But the essential point here is not the internal precision but what is returned to the user. Do the 12C Platinum or 12C+ (real hardware) return 10 or 12 digits? In both cases the display has 10 digits. What do you see after 3 [1/x] 30 [x] in FIX 9 mode? 10,00000000 or 9,999999999 ?

12C+: 9.999999999
12C Emulator: 9.999999999
12CP: 10.00000000
12CP Emulator: 10.00000000

(09-13-2018 06:35 PM)Dieter Wrote:  Also, could you or someone else please do the following test on a hardware 12C Platinum or 12C+? As already mentioned in my previous post:

Quote:You may try this: calculate 4.444.444.444 / 3 and get 1.481.481.481. Now subtract 1.481.481.481 (or press g FRAC). On a real 12C the result is 0. But what do you get on the 12CP emulator? 0,3? 0,333? Please post all digits (i.e. as displayed in FIX 9).

12C+: 0.000000000
12C Emulator: 0.000000000
12CP: 0.330000000
12CP Emulator: 0.333330000 <=== wink, wink, nudge, nudge, say no more!

[Albert Chan]

(09-13-2018 08:52 PM)rprosperi Wrote:  12C+: 0.000000000
12C Emulator: 0.000000000
12CP: 0.330000000
12CP Emulator: 0.333330000 <=== wink, wink, nudge, nudge, say no more!

I was curious, which answer you preferred most ?
The wink, wink can be intepreted either way

there is beauty in what you see is what you get ... but, more precision is better

[rprosperi]

(09-13-2018 09:35 PM)Albert Chan Wrote:  

(09-13-2018 08:52 PM)rprosperi Wrote:  12C+: 0.000000000
12C Emulator: 0.000000000
12CP: 0.330000000
12CP Emulator: 0.333330000 <=== wink, wink, nudge, nudge, say no more!

I was curious, which answer you preferred most ?
The wink, wink can be intepreted either way

there is beauty in what you see is what you get ... but, more precision is better

0.330000000 is without question the right answer. The emulator, by definition, must return the exact same results as the machine it is emulating, even if the emulator's answer is theoretically more accurate.

Sorry if my Python quote was misleading, it's just what popped into my head when I saw the result, 'no need to say any more'.

[Dieter]

(09-13-2018 08:52 PM)rprosperi Wrote:  12C+: 9.999999999
12C Emulator: 9.999999999
12CP: 10.00000000
12CP Emulator: 10.00000000
...
12C Emulator: 0.000000000
12CP: 0.330000000
12CP Emulator: 0.333330000 <=== wink, wink, nudge, nudge, say no more!

Thank you, Bob. Very enlightening, indeed. So the emulator does not seem to round the internal 15-digit result back to 12 digits. I wonder if this also applies to other functions. What does frac(sqrt(2E8)) return? 0,1356237 or are there more decimals? In the latter case the final digit(s) may be slightly off. 15 digits internal precision does not mean that in the end all 15 are correct.

Anyway, the emulator obviously does not emulate a 12C Platinum. This means that it can and will produce results that do not match those from a hardware calculator.

As the 12C and 12C Platinum have different precision this also means that 12C programs can give other results if run on the 12C Platinum. I wonder if this also applies to the working range: usually the 12-digit calculators operate in a domain of 1E–499 to 9,999...E+499. Is this also true for the 12C Platinum? Does e^500 produce an overflow error or does it return 1,40359...E+217 ?

Dieter

[rprosperi]

(09-14-2018 12:18 PM)Dieter Wrote:  Thank you, Bob. Very enlightening, indeed. So the emulator does not seem to round the internal 15-digit result back to 12 digits. I wonder if this also applies to other functions. What does frac(sqrt(2E8)) return? 0,1356237 or are there more decimals? In the latter case the final digit(s) may be slightly off. 15 digits internal precision does not mean that in the end all 15 are correct.

12C+: 0.135620000 (Note: I am using the preceding "E" to be clear, but these are not actually displayed, there is simply a space)
12C Emulator: 0.135620000
12CP: 0.135623700
12CP Emulator: 0.135623731 <=== Again, deviation from correct behavior

(09-14-2018 12:18 PM)Dieter Wrote:  As the 12C and 12C Platinum have different precision this also means that 12C programs can give other results if run on the 12C Platinum. I wonder if this also applies to the working range: usually the 12-digit calculators operate in a domain of 1E–499 to 9,999...E+499. Is this also true for the 12C Platinum? Does e^500 produce an overflow error or does it return 1,40359...E+217 ?

12C+: 9.999999 E99
12C Emulator: 9.999999 E99
12CP: 9.999999 E99
12CP Emulator: 9.999999 E99

From the 12C Manual on p. 84 (exact same content is also in the 12CP manual):

Quote:Overflow and Underflow. If a calculation results in a number
whose magnitude is greater than 9.999999999 X 10^99 the
calculation is halted and the calculator displays 9.999999 99 (if
the number is positive) or -9.999999 99 (if the number is
negative).

If a calculation results in a number whose magnitude is less than 10-99,
the calculation is not halted, but the value 0 is used for that
number in subsequent calculations.

I never noticed this before, but I don't see any specific description of the supported numeric range in either manual.

[Dieter]

(09-14-2018 04:19 PM)rprosperi Wrote:  12C+: 0.135620000 (Note: I am using the preceding "E" to be clear, but these are not actually displayed, there is simply a space)
12C Emulator: 0.135620000
12CP: 0.135623700
12CP Emulator: 0.135623731 <=== Again, deviation from correct behavior

...but at least correctly rounded. There should be one more digit on the 12C Platinum emulator. What do you get if you multiply the result by 10? The true value of sqrt(2) is 1,4142135623730950488... so the emulator should show 1,356237310 (when correctly rounded up) or at least 1,356237309 (when truncated after the 15th digit, as the internal routines often do – think of the 5^2 – 25 example).

(09-14-2018 04:19 PM)rprosperi Wrote:  12C+: 9.999999 E99
12C Emulator: 9.999999 E99
12CP: 9.999999 E99
12CP Emulator: 9.999999 E99

So there is no extended working range. Maybe this is due to the limited display space.

Dieter

[rprosperi]

(09-14-2018 06:33 PM)Dieter Wrote:  What do you get if you multiply the result by 10? The true value of sqrt(2) is 1,4142135623730950488... so the emulator should show 1,356237310 (when correctly rounded up) or at least 1,356237309 (when truncated after the 15th digit, as the internal routines often do – think of the 5^2 – 25 example).

When multiplied by 10, the result is 1.356237309, so it appears truncation rather than rounding is used on the 12CP emulator. Most likely though is this is just an error, retaining the full value from the underlying C math; unlike the 12c emulator running the original ROM, perhaps the 12CP was recompiled for the new Android cpu, "bringing along" the extra digits which are then crammed into the 10-digit display routines.

On the real 12CP, result is 1.356237000, as expected.