(12C) Check if given number is Prime Number or not
09-10-2018, 06:48 PM
Post: #3
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) Check if given number is Prime Number or not
(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
 « Next Oldest | Next Newest »

 Messages In This Thread (12C) Check if given number is Prime Number or not - Gamo - 09-10-2018, 08:49 AM RE: (12C) Check if given number is Prime Number or not - Joe Horn - 09-10-2018, 04:16 PM RE: (12C) Check if given number is Prime Number or not - Dieter - 09-10-2018 06:48 PM RE: (12C) Check if given number is Prime Number or not - Albert Chan - 09-10-2018, 10:18 PM RE: (12C) Check if given number is Prime Number or not - Thomas Klemm - 09-11-2018, 03:12 AM RE: (12C) Check if given number is Prime Number or not - Gamo - 09-11-2018, 05:42 AM RE: (12C) Check if given number is Prime Number or not - Dieter - 09-11-2018, 07:18 AM RE: (12C) Check if given number is Prime Number or not - Thomas Klemm - 09-11-2018, 06:45 AM RE: (12C) Check if given number is Prime Number or not - Gamo - 09-11-2018, 08:03 AM RE: (12C) Check if given number is Prime Number or not - Dieter - 09-13-2018, 06:35 PM RE: (12C) Check if given number is Prime Number or not - rprosperi - 09-13-2018, 08:52 PM RE: (12C) Check if given number is Prime Number or not - Albert Chan - 09-13-2018, 09:35 PM RE: (12C) Check if given number is Prime Number or not - rprosperi - 09-13-2018, 11:21 PM RE: (12C) Check if given number is Prime Number or not - Dieter - 09-14-2018, 12:18 PM RE: (12C) Check if given number is Prime Number or not - rprosperi - 09-14-2018, 04:19 PM RE: (12C) Check if given number is Prime Number or not - Dieter - 09-14-2018, 06:33 PM RE: (12C) Check if given number is Prime Number or not - rprosperi - 09-14-2018, 08:15 PM

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