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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: