Programming Praxis

Checking Primality

October 21, 2016 9:00 AM

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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

9 Responses to “Checking Primality”

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

By Jussi Piitulainen on October 21, 2016 at 12:39 PM

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

By Zack on October 21, 2016 at 4:09 PM
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);}

By Bill on October 22, 2016 at 12:29 AM

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)

By matthew on October 22, 2016 at 8:32 AM

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)

By Jussi Piitulainen on October 23, 2016 at 7:21 AM

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

By Milbrae on October 23, 2016 at 9:11 AM

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

By matthew on October 23, 2016 at 9:16 AM

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

By matthew on October 23, 2016 at 10:00 AM

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

By Jussi Piitulainen on October 24, 2016 at 8:08 AM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Checking Primality

Share this:

Related

9 Responses to “Checking Primality”

Leave a Reply