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

[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