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.

Pages: 1 2

9 Responses to “Checking Primality”

  1. Jussi Piitulainen said

    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")
    end
    
  2. Zack said

    That’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

  3. Bill said

    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);}

  4. matthew said

    If they are struggling with loops and variables then maybe a more functional approach would be better, for example, in ES6:

    let prime = n => n >= 2 && checkfrom(n,2)
    let checkfrom = (n,i) => i == n || mod(n,i,0,0) != 0 && checkfrom(n,i+1)
    let mod = (n,i,j,c) => c == i ? mod(n,i,j,0) : j == n ? c : mod(n,i,j+1,c+1)
    
    for (let i = 0; i < 100; i++) if (prime(i)) console.log(i)
    
  5. Jussi Piitulainen said

    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)
    
  6. Milbrae said

    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;
    }
    
  7. matthew said

    @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/

  8. matthew said

    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])
    
  9. Jussi Piitulainen said

    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.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: