(12C) Check if given number is Prime Number or not
09-10-2018, 10:18 PM (This post was last modified: 09-11-2018 08:16 PM by Albert Chan.)
Post: #4
 Albert Chan Senior Member Posts: 682 Joined: Jul 2018
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 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
 « 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)