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

09102018, 08:49 AM
(This post was last modified: 09102018 09:02 AM by Gamo.)
Post: #1




(12C) Check if given number is Prime Number or not
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:
Remark: The larger the number the longer time it takes to give result even on HP12C+ 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 HP12C emulator this program run extremely fast. Gamo 

09102018, 04:16 PM
Post: #2




RE: (12C) Check if given number is Prime Number or not
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.
<0ɸ0> Joe 

09102018, 06:48 PM
Post: #3




RE: (12C) Check if given number is Prime Number or not
(09102018 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). (09102018 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 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 

09102018, 10:18 PM
(This post was last modified: 09112018 08:16 PM by Albert Chan.)
Post: #4




RE: (12C) Check if given number is Prime Number or not
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 225199 = 26 16 +31 => 57, 17 +33 => 90, STOP, N is Prime Try N = 1403, 40^2=1600, 39^2=160079=1521, 38^2=152177=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 14441403 = 41 39 +77 => 118 40 +79 => 197 41 +81 => 278 42 +83 => 361 = 19^2, thus 1403 = (4219)(42+19) = 23*61, a composite 

09112018, 03:12 AM
Post: #5




RE: (12C) Check if given number is Prime Number or not
This works only for odd numbers. (Cf. Fermat's factorization method)
Code: 01 STO 0 ; N 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 

09112018, 05:42 AM
Post: #6




RE: (12C) Check if given number is Prime Number or not
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 HP12C, 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 

09112018, 06:45 AM
Post: #7




RE: (12C) Check if given number is Prime Number or not
(09112018 05:42 AM)Gamo Wrote: Is this another rounding problem on the 12C ? Yes. Since the real HP12C 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 And thus the program tells you erroneously that this number is divisible by 2. HTH Thomas 

09112018, 07:18 AM
(This post was last modified: 09112018 07:38 AM by Dieter.)
Post: #8




RE: (12C) Check if given number is Prime Number or not
(09112018 05:42 AM)Gamo Wrote: The prime number is 9,000,000,001 As Thomas already pointed out, the problem is the 12C's 10digit 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 10digit 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 

09112018, 08:03 AM
(This post was last modified: 09112018 11:16 AM by Gamo.)
Post: #9




RE: (12C) Check if given number is Prime Number or not
Just check the spec sheet on HP12C 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 Hp12C+ (not original edition) Display 1 and speed took about 2 minutes Gamo 

09132018, 06:35 PM
Post: #10




RE: (12C) Check if given number is Prime Number or not
(09112018 08:03 AM)Gamo Wrote: Just check the spec sheet on HP12C Platinum 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 

09132018, 08:52 PM
Post: #11




RE: (12C) Check if given number is Prime Number or not
(09132018 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 (09132018 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: 12C+: 0.000000000 12C Emulator: 0.000000000 12CP: 0.330000000 12CP Emulator: 0.333330000 <=== wink, wink, nudge, nudge, say no more! Bob Prosperi 

09132018, 09:35 PM
Post: #12




RE: (12C) Check if given number is Prime Number or not
(09132018 08:52 PM)rprosperi Wrote: 12C+: 0.000000000 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 

09132018, 11:21 PM
Post: #13




RE: (12C) Check if given number is Prime Number or not
(09132018 09:35 PM)Albert Chan Wrote:(09132018 08:52 PM)rprosperi Wrote: 12C+: 0.000000000 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'. Bob Prosperi 

09142018, 12:18 PM
Post: #14




RE: (12C) Check if given number is Prime Number or not
(09132018 08:52 PM)rprosperi Wrote: 12C+: 9.999999999 Thank you, Bob. Very enlightening, indeed. So the emulator does not seem to round the internal 15digit 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 12digit 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 

09142018, 04:19 PM
Post: #15




RE: (12C) Check if given number is Prime Number or not
(09142018 12:18 PM)Dieter Wrote: Thank you, Bob. Very enlightening, indeed. So the emulator does not seem to round the internal 15digit 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 (09142018 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 12digit 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 I never noticed this before, but I don't see any specific description of the supported numeric range in either manual. Bob Prosperi 

09142018, 06:33 PM
(This post was last modified: 09142018 06:35 PM by Dieter.)
Post: #16




RE: (12C) Check if given number is Prime Number or not
(09142018 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) ...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). (09142018 04:19 PM)rprosperi Wrote: 12C+: 9.999999 E99 So there is no extended working range. Maybe this is due to the limited display space. Dieter 

09142018, 08:15 PM
Post: #17




RE: (12C) Check if given number is Prime Number or not
(09142018 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 10digit display routines. On the real 12CP, result is 1.356237000, as expected. Bob Prosperi 

« Next Oldest  Next Newest »

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