Checking Primality
October 21, 2016
[ I haven’t had time to prepare a new exercise because I’ve been busy finishing up a big project at work. So the bad news is we have a repeat exercise, but the good news is that my project is done! ]
We have today an exercise that has appeared on message boards at least a dozen times in the last few weeks; it must be that time in the semester when beginning programming students are working on their mid-term homework assignments.
Write a program that, given an integer, determines whether or not it is prime.
Your task is to write a program that determines if a given integer is prime, in the style of a beginning programmer who is less than confident of his knowledge of variable assignment and loops; do not use a complicated algorithm. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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.)