Checking Primality
October 21, 2016
We’ll use a simple trial-division algorithm, starting from 2 and working up to the square root of the input number n; note that we don’t have to go beyond the square root because, if n = p q, one or the other of p or q must be less than the square root. Here’s our solution, in an algol-like pseudocode so students can translate it to C or Java or whatever is their teaching language:
function isPrime(n)
f := 2
while f * f <= n
if n % f == 0
return False
f := f + 1
return True
Instead of computing the square root of n, we compute the square of f because floating-point square root calculations might lose precision. The limit is compared using the <= operator rather than < because perfect squares would be reported as prime otherwise. We stop immediately, and return False, if n is divisible by the current f; there is no need to continue the trial division because we know the answer. An easy optimization is to consider 2 as the only even trial divisor, because any larger even trial divisor will certainly not divide n:
function isPrime(n)
if n % 2 == 0
return n == 2
f := 3
while f * f <= n
if n % f == 0
return False
f := f + 2
return True
Note that the return on even numbers is n == 2 rather than just False because 2 would improperly be reported as composite otherwise.
There are better ways to determine the primality of numbers, especially large numbers, but this is sufficient for small numbers and beginning programmers.
Programming Praxis 
Algol 60 (using Marst 2.7) where I actually am the beginner who is not too confident. This program reads a written representation of a (small) positive integer from stdin, counts its divisors, and reports in stdout whether the named integer is prime (in the sense of having exactly two divisors). Here the “per cent” operator is integer division; I did not find any remainder operator.
begin integer procedure number of divisors(n); value n; integer n; begin integer k, count; count := 0; for k := 1 step 1 until n do count := count + (if (n % k) * k = n then 1 else 0); number of divisors := count end; boolean procedure is prime(n); value n; integer n; is prime := (number of divisors(n) = 2); integer arg; ininteger(0, arg); outinteger(1, arg); if is prime(arg) then outstring(1, "is prime\n") else outstring(1, "is not prime\n") endThat’s a classic! Here is my take on it using Julia. Probably not the most efficient algorithm out there, but since the emphasis is on getting something that works and get it out there fast, I focused on minimizing the implementation time.
function is_prime(x::Int64)
if div(x, 2) == 0; return false; end
z = round(Int64, sqrt(x))
for n = 3:2:z
if x % n == 0; return false; end
end
return true
end
Here is code written in Pari/GP using a custom approach. It uses Pari’s built-in divisors function. No claim to compactness or efficiency on larger composites. It checks the first 100 prime factor divisors for speed, but that is optional.
binPrime(candidate)={
if(candidate==2||candidate==3||candidate==5,return(1));
if(candidate<2||candidate%5==0||candidate%2==0,return(0));
myRem=candidate%6;
if(myRem%6!=1&&myRem%6!=5, return(0) );
for(j5=2,100,if(candidate!=prime(j5)&&candidate%prime(j5)==0, return(0) ) );
if(myRem==1, F=-(candidate-1)/2-1);
if(myRem==5, F=-(candidate+1)/2);
coreList=List();
k=-4*(2+4*F);
coreList=divisors(k/2);
for(i5=1,length(coreList),d=coreList[i5];
x=(k/(2*d)-d+4)/4;
y=(d-2)/4;
if(x<1||y<1,next );
if(truncate(x)!=x||truncate(y)!=y,next);
return(0)
);\\end FOR i5
return(1);}
If they are struggling with loops and variables then maybe a more functional approach would be better, for example, in ES6:
Opinions differ on what is an advanced concept. And on many other things :)
(define (greatest-divisor n) ;integer n > 1 (let seek ((k (- 1 n))) ;This is not a loop :| (if (zero? (remainder n k)) (- k) (seek (+ k 1))))) (define (prime? n) (and (> n 1) (= (greatest-divisor n) 1))) (write (filter prime? '(1 2 3 4 5 6 7 8 9 10 11 12 13 14))) ;;displays: (2 3 5 7 11 13)I think the concept of trial division is the most common, nothing too taxing IMHO. Here’s my code in D…
bool isPrime(uint n) { if (n < 6) return ((n == 2) || (n == 3) || (n == 5)); if ((n % 2 == 0) || (n % 3 == 0) || (n % 5 == 0)) return false; uint d = 7; while (d * d <= n) { if (n % d == 0) return false; d = d + 2; } return true; }@Jussi: My local college has been starting the kids off on functional stuff for a while:
http://www.cl.cam.ac.uk/teaching/1617/FoundsCS/
Maybe this Haskell program is better (and using the succ operation makes explicit that we are using no more advanced concepts than recursion, successor and equality):
#!/usr/bin/runghc prime n = n >= 2 && check 2 0 0 where check i j c | i == n = True | c == i = check i j 0 | j == n = c /= 0 && check (succ i) 0 0 | otherwise = check i (succ j) (succ c) main = print (filter prime [0..100])Yes, @matthew, I certainly agree that recursion (after functional abstraction) is a most basic thing. Good for your college.
It’s sad that some people still learn recursion as some difficult “advanced technique”, but I think they do, and I suspect those imaginary students who struggle with variable assignment and loops may be heading that way. Perhaps they learn their while and for loops and remain nervous about recursion. Or maybe I live too much in the past? Hopefully.
I learnt mostly from Scheme literature, including but not limited to SICP, where everything was seen as built ultimately from procedural abstraction, procedure calls (with bounded-space tail-calls), conditional expressions, variable references, literal data, and a number of primitive procedures (some of them rather special). Oh, and variable assignment, I almost forgot that :) But then one is expected to know those few basic things well. Recursive scope leads to recursive procedures, which then contain loops as an important special case.
The courses they offered in my university were different. More focused on the while-loop in Pascal back then, and then with Java came all that comes with Java. (Nowadays I associate Java with litigation. To be avoided.)