Primality by trial division

Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime.

Use trial division. Even numbers over two may be eliminated right away. A loop from 3 to √n will suffice, but other loops are allowed.

Related tasks: Sieve of Eratosthenes, Prime decomposition, AKS test for primes.

ACL2

<lang Lisp>(defun is-prime-r (x i)

  (declare (xargs :measure (nfix (- x i))))
  (if (zp (- (- x i) 1))
      t
      (and (/= (mod x i) 0)
           (is-prime-r x (1+ i)))))

(defun is-prime (x)

  (or (= x 2)
      (is-prime-r x 2)))</lang>

<lang ActionScript>function isPrime(n:int):Boolean { if(n < 2) return false; if(n == 2) return true; if((n & 1) == 0) return false; for(var i:int = 3; i <= Math.sqrt(n); i+= 2) if(n % i == 0) return false; return true; }</lang>

Ada

<lang ada>function Is_Prime(Item : Positive) return Boolean is

  Result : Boolean := True;
  Test : Natural;

begin

  if Item /= 2 and Item mod 2 = 0 then
     Result := False;
  else
     Test := 3;
     while Test < Integer(Sqrt(Float(Item))) loop
        if Item mod Test = 0 then
           Result := False;
           exit;
        end if;
        Test := Test + 2;
     end loop;
 end if;
 return Result;

end Is_Prime;</lang>

ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

COMMENT
  This routine is used in more than one place, and is essentially a
  template that can by used for many different types, eg INT, LONG INT...
USAGE
  MODE ISPRIMEINT = INT, LONG INT, etc
  PR READ "prelude/is_prime.a68" PR
END COMMENT

PROC is prime = ( ISPRIMEINT p )BOOL:
  IF p <= 1 OR ( NOT ODD p AND p/= 2) THEN
    FALSE
  ELSE
    BOOL prime := TRUE;
    FOR i FROM 3 BY 2 TO ENTIER sqrt(p)
      WHILE prime := p MOD i /= 0 DO SKIP OD;
    prime
  FI

<lang algol68>main:(

 INT upb=100;
 printf(($" The primes up to "g(-3)" are:"l$,upb));
 FOR i TO upb DO 
   IF is prime(i) THEN
     printf(($g(-4)$,i))
   FI
 OD;
 printf($l$)

)</lang>

Output:

The primes up to 100 are:
   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97

AutoHotkey

Discussion <lang autohotkey>MsgBox % IsPrime(1995937) Loop

  MsgBox % A_Index-3 . " is " . (IsPrime(A_Index-3) ? "" : "not ") . "prime."

IsPrime(n,k=2) { ; testing primality with trial divisors not multiple of 2,3,5, up to sqrt(n)

  d := k+(k<7 ? 1+(k>2) : SubStr("6-----4---2-4---2-4---6-----2",Mod(k,30),1)) 
  Return n < 3 ? n>1 : Mod(n,k) ? (d*d <= n ? IsPrime(n,d) : 1) : 0

}</lang>

AutoIt

<lang autoit>#cs ----------------------------------------------------------------------------

AutoIt Version: 3.3.8.1
Author:         Alexander Alvonellos

Script Function:

Perform primality test on a given integer $number. RETURNS: TRUE/FALSE

ce ----------------------------------------------------------------------------

Func main() ConsoleWrite("The primes up to 100 are: " & @LF) For $i = 1 To 100 Step 1 If(isPrime($i)) Then If($i <> 97) Then ConsoleWrite($i & ", ") Else ConsoleWrite($i) EndIf EndIf Next EndFunc

Func isPrime($n) If($n < 2) Then Return False If($n = 2) Then Return True If(BitAnd($n, 1) = 0) Then Return False For $i = 3 To Sqrt($n) Step 2 If(Mod($n, $i) = 0) Then Return False Next Return True EndFunc main()</lang>

AWK

$ awk 'func prime(n){for(d=2;d<=sqrt(n);d++)if(!(n%d)){return 0};return 1}{print prime($1)}'

Or more legibly, and with n <= 1 handling

<lang AWK>function prime(n) {

   if (n <= 1) return 0
   for (d = 2; d <= sqrt(n); d++)
       if (!(n % d)) return 0
   return 1

}

{print prime($1)}</lang>

BASIC

Works with: QuickBasic version 4.5

Returns 1 for prime, 0 for non-prime <lang QBasic>FUNCTION prime% (n!)

 STATIC i AS INTEGER
 IF n = 2 THEN
   prime = 1
 ELSEIF n <= 1 OR n MOD 2 = 0 THEN
   prime = 0
 ELSE
   prime = 1
   FOR i = 3 TO INT(SQR(n)) STEP 2
     IF n MOD i = 0 THEN
       prime = 0
       EXIT FUNCTION
     END IF
   NEXT i
 END IF

END FUNCTION

' Test and display primes 1 .. 50 DECLARE FUNCTION prime% (n!) FOR n = 1 TO 50

 IF prime(n) = 1 THEN PRINT n;

NEXT n</lang>

Output:

 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47

ZX Spectrum Basic

<lang ZXBasic>10 LET n=0: LET p=0 20 INPUT "Enter number: ";n 30 GO SUB 1000 40 IF p=0 THEN PRINT n;" is not prime!" 50 IF p<>0 THEN PRINT n;" is prime!" 60 GO TO 10 1000 REM *************** 1001 REM * PRIME CHECK * 1002 REM *************** 1010 LET p=0 1020 IF n/2=INT (n/2) THEN RETURN 1030 LET p=1 1040 FOR i=3 TO SQR (n) STEP 2 1050 IF n/i=INT (n/i) THEN LET p=0: LET i= SQR (n) 1060 NEXT i 1070 RETURN </lang>

Output:

15 is not prime!
17 is prime!
119 is not prime!
137 is prime!

BBC BASIC

<lang bbcbasic> FOR i% = -1 TO 100

       IF FNisprime(i%) PRINT ; i% " is prime"
     NEXT
     END
     
     DEF FNisprime(n%)
     IF n% <= 1 THEN = FALSE
     IF n% <= 3 THEN = TRUE
     IF (n% AND 1) = 0 THEN = FALSE
     LOCAL t%
     FOR t% = 3 TO SQR(n%) STEP 2
       IF n% MOD t% = 0 THEN = FALSE
     NEXT
     = TRUE</lang>

Output:

2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime

bc

<lang bc>/* Return 1 if n is prime, 0 otherwise */ define p(n) {

   auto i

   if (n < 2) return(0)
   if (n == 2) return(1)
   if (n % 2 == 0) return(0)
   for (i = 3; i * i <= n; i += 2) {
       if (n % i == 0) return(0)
   }
   return(1)

}</lang>

Bracmat

<lang bracmat> ( prime

 =   incs n I inc
   .   4 2 4 2 4 6 2 6:?incs
     & 2:?n
     & 1 2 2 !incs:?I
     &   whl
       ' ( !n*!n:~>!arg
         & div$(!arg.!n)*!n:~!arg
         & (!I:%?inc ?I|!incs:%?inc ?I)
         & !n+!inc:?n
         )
     & !n*!n:>!arg
 )

& 100000000000:?p & whl

 ' ( !p+1:<100000000100:?p
   & (   prime$!p
       & out$!p
     | 
     )
   )

& ;</lang>

Output:

100000000003
100000000019
100000000057
100000000063
100000000069
100000000073
100000000091

Burlesque

Implicit trial division is done by the fc function. It checks if the number has exactly two divisors.

Version not using the fc function:

Explanation. Given n generates a block containing 2..n-1. Calculates a block of modolus and check if it contains 0. If it contains 0 it is not a prime.

C

<lang c>int is_prime(unsigned int n) { unsigned int p; if (!(n & 1) || n < 2 ) return n == 2;

/* comparing p*p <= n can overflow */ for (p = 3; p <= n/p; p += 2) if (!(n % p)) return 0; return 1; }</lang>

C++

<lang cpp>#include <cmath>

bool is_prime(unsigned int n) {

   if (n <= 1)
       return false;
   if (n == 2)
       return true;
   for (unsigned int i = 2; i <= sqrt(n); ++i)
       if (n % i == 0)
           return false;
   return true;

}</lang>

C#

<lang csharp>static bool isPrime(int n)

       {
           if (n <= 1) return false;
           for (int i = 2; i * i <= n; i++)            
               if (n % i == 0) return false;            
           return true;
       }</lang>

Chapel

Translation of: C++

<lang chapel>proc is_prime(n) {

   if n == 2 then
       return true;
   if n <= 1 || n % 2 == 0 then
       return false;
   for i in 3..floor(sqrt(n)):int by 2 do
       if n % i == 0 then
           return false;
   return true;

}</lang>

Clojure

The symbol # is a shortcut for creating lambda functions; the arguments in such a function are %1, %2, %3... (or simply % if there is only one argument). Thus, #(< (* % %) n) is equivalent to (fn [x] (< (* x x) n)) or more mathematically f(x) = x * x < n. <lang clojure>(defn divides? [k n] (= (rem n k) 0))

(defn prime? [n]

 (if (< n 2)
   false
   (empty? (filter #(divides? % n) (take-while #(<= (* % %) n) (range 2 n))))))</lang>

CMake

<lang cmake># Prime predicate: does n be a prime number? Sets var to true or false. function(primep var n)

 if(n GREATER 2)
   math(EXPR odd "${n} % 2")
   if(odd)
     # n > 2 and n is odd.
     set(factor 3)
     # Loop for odd factors from 3, while factor <= n / factor.
     math(EXPR quot "${n} / ${factor}")
     while(NOT factor GREATER quot)
       math(EXPR rp "${n} % ${factor}")        # Trial division
       if(NOT rp)
         # factor divides n, so n is not prime.
         set(${var} false PARENT_SCOPE)
         return()
       endif()
       math(EXPR factor "${factor} + 2")       # Next odd factor
       math(EXPR quot "${n} / ${factor}")
     endwhile(NOT factor GREATER quot)
     # Loop found no factor, so n is prime.
     set(${var} true PARENT_SCOPE)
   else()
     # n > 2 and n is even, so n is not prime.
     set(${var} false PARENT_SCOPE)
   endif(odd)
 elseif(n EQUAL 2)
   set(${var} true PARENT_SCOPE)       # 2 is prime.
 else()
   set(${var} false PARENT_SCOPE)      # n < 2 is not prime.
 endif()

endfunction(primep)</lang>

<lang cmake># Quick example. foreach(i -5 1 2 3 37 39)

 primep(b ${i})
 if(b)
   message(STATUS "${i} is prime.")
 else()
   message(STATUS "${i} is _not_ prime.")
 endif(b)

endforeach(i)</lang>

COBOL

<lang cobol> Identification Division.

      Program-Id. Primality-By-Subdiv.

      Data Division.
      Working-Storage Section.
      78  True-Val  Value 0.
      78  False-Val Value 1.

      Local-Storage Section.
      01  lim Pic 9(10).
      01  i   Pic 9(10).

      Linkage Section.
      01  num    Pic 9(10).
      01  result Pic 9.

      Procedure Division Using num result.
      Main.
          If num <= 1
              Move False-Val To result
              Goback
          Else If num = 2
              Move True-Val To result
              Goback
          End-If

          Compute lim = Function Sqrt(num) + 1
          Perform Varying i From 3 By 1 Until lim < i
              If Function Mod(num, i) = 0
                  Move False-Val To result
                  Goback
              End-If
          End-Perform

          Move True-Val To Result

          Goback
          .</lang>

CoffeeScript

<lang coffeescript>is_prime = (n) ->

 # simple prime detection using trial division, works
 # for all integers
 return false if n <= 1 # by definition
 p = 2
 while p * p <= n
   return false if n % p == 0
   p += 1
 true

for i in [-1..100]

 console.log i if is_prime i</lang>

Common Lisp

<lang Lisp> (defun primep (a)

 (cond ((= a 2) T)
       ((or (<= a 1) (= (mod a 2) 0)) nil)
       ((loop for i from 3 to (sqrt a) by 2 do
               (if (= (mod a i) 0)
                   (return nil))) nil)
       (T T)))</lang>

<lang Lisp>(defun primep (n)

 "Is N prime?"
 (and (> n 1) 
      (or (= n 2) (oddp n))
      (loop for i from 3 to (isqrt n) by 2

never (zerop (rem n i)))))</lang>

D

Simple Version

<lang d>import std.stdio, std.algorithm, std.range, std.math;

bool isPrime1(in int n) pure nothrow {

   if (n == 2)
       return true;
   if (n <= 1 || (n & 1) == 0)
       return false;

   for(int i = 3; i <= real(n).sqrt; i += 2)
       if (n % i == 0)
           return false;
   return true;

}

void main() {

   iota(2, 40).filter!isPrime1.writeln;

}</lang>

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Version with excluded multiplies of 2 and 3

Same output. <lang d>bool isPrime2(It)(in It n) pure nothrow {

   // Adapted from: http://www.devx.com/vb2themax/Tip/19051
   // Test 1, 2, 3 and multiples of 2 and 3:
   if (n == 2 || n == 3)
       return true;
   else if (n < 2 || n % 2 == 0 || n % 3 == 0)
       return false;

   // We can now avoid to consider multiples of 2 and 3. This
   // can be done really simply by starting at 5 and
   // incrementing by 2 and 4 alternatively, that is:
   //   5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
   // We don't need to go higher than the square root of the n.
   for (It div = 5, inc = 2; div ^^ 2 <= n; div += inc, inc = 6 - inc)
       if (n % div == 0)
           return false;

   return true;

}

void main() {

   import std.stdio, std.algorithm, std.range;

   iota(2, 40).filter!isPrime2.writeln;

}</lang>

Two Way Test

Odd divisors is generated both from increasing and decreasing sequence, may improve performance for numbers that have large minimum factor. Same output. <lang d>import std.stdio, std.algorithm, std.range, std.math;

bool isPrime3(T)(in T n) pure nothrow {

   if (n % 2 == 0 || n <= 1)
       return n == 2;
   T head = 3, tail = (cast(T)real(n).sqrt / 2) * 2 + 1;
   for ( ; head <= tail ; head +=2, tail -= 2)
       if ((n % head) == 0 || (n % tail) == 0)
           return false;
   return true;

}

void main() {

   iota(2, 40).filter!isPrime3.writeln;

}</lang>

Delphi

First

<lang Delphi>function IsPrime(aNumber: Integer): Boolean; var

 I: Integer;

begin

 Result:= True;
 if(aNumber = 2) then Exit;

 Result:= not ((aNumber mod 2 = 0)  or
               (aNumber <= 1));
 if not Result then Exit;

 for I:=3 to Trunc(Sqrt(aNumber)) do
 if(aNumber mod I = 0) then
 begin
   Result:= False;
   Break;
 end;

end;</lang>

Second

<lang Delphi>function IsPrime(const x: integer): Boolean; var

 i: integer;

begin

 i := 2;
 repeat
   if X mod i = 0 then
   begin
     Result := False;
     Exit;
   end;
   Inc(i);
 until i > Sqrt(x);
 Result := True;

end;</lang>

E

Translation of: D

<lang e>def isPrime(n :int) {

   if (n == 2) {
       return true
   } else if (n <= 1 || n %% 2 == 0) {
       return false
   } else {
       def limit := (n :float64).sqrt().ceil()
       var divisor := 1
       while ((divisor += 2) <= limit) {
           if (n %% divisor == 0) {
               return false
           }
       }
       return true
   }

}</lang>

Emacs Lisp

Use cl.el library. <lang lisp> (defun prime (a)

 (not (or (< a 2)
          (loop for x from 2 to (sqrt a)
                when (zerop (% a x))
                return t))))

</lang> More concise, a little bit faster: <lang lisp> (defun prime2 (a)

 (and (> a 1)
      (loop for x from 2 to (sqrt a)
            never (zerop (% a x)))))

</lang> A little bit faster: <lang lisp> (defun prime3 (a)

 (and (> a 1)
      (or (= a 2) (oddp a))
      (loop for x from 3 to (sqrt a) by 2
            never (zerop (% a x)))))

</lang> More than 2 times faster, than the previous, doesn't use loop macro: <lang lisp> (defun prime4 (a)

 (not (or (< a 2)
          (some (lambda (x) (zerop (% a x))) (number-sequence 2 (sqrt a))))))

</lang> Almost 2 times faster, than the previous: <lang lisp> (defun prime5 (a)

 (not (or (< a 2)
          (and (/= a 2) (evenp a))
          (some (lambda (x) (zerop (% a x))) (number-sequence 3 (sqrt a) 2)))))

</lang>

Erlang

<lang erlang>is_prime(N) when N == 2 -> true; is_prime(N) when N < 2 orelse N rem 2 == 0 -> false; is_prime(N) -> is_prime(N,3).

is_prime(N,K) when K*K > N -> true; is_prime(N,K) when N rem K == 0 -> false; is_prime(N,K) -> is_prime(N,K+2).</lang>

Euphoria

<lang euphoria>function is_prime(integer n)

   if n<=2 or remainder(n,2)=0 then
       return 0
   else
       for i=3 to sqrt(n) by 2 do
           if remainder(n,i)=0 then
               return 0
           end if
       end for
       return 1
   end if

end function</lang>

Factor

<lang factor>USING: combinators kernel math math.functions math.ranges sequences ;

prime? ( n -- ? )

   {
       { [ dup 2 < ] [ drop f ] }
       { [ dup even? ] [ 2 = ] }
       [ 3 over sqrt 2 <range> [ mod 0 > ] with all? ]
   } cond ;</lang>

FALSE

<lang false>[0\$2=$[@~@@]?~[$$2>\1&&[\~\

  3[\$@$@1+\$*>][\$@$@$@$@\/*=[%\~\$]?2+]#%

]?]?%]p:</lang>

FBSL

The second function (included by not used) I would have thought would be faster because it lacks the SQR() function. As it happens, the first is over twice as fast. <lang qbasic>#APPTYPE CONSOLE

FUNCTION ISPRIME(n AS INTEGER) AS INTEGER

   IF n = 2 THEN
       RETURN TRUE
   ELSEIF n <= 1 ORELSE n MOD 2 = 0 THEN
       RETURN FALSE
   ELSE
       FOR DIM i = 3 TO SQR(n) STEP 2
           IF n MOD i = 0 THEN
               RETURN FALSE
           END IF
       NEXT
       RETURN TRUE
   END IF

END FUNCTION

FUNCTION ISPRIME2(N AS INTEGER) AS INTEGER

   IF N <= 1 THEN RETURN FALSE
   DIM I AS INTEGER = 2
   WHILE I * I <= N
       IF N MOD I = 0 THEN
           RETURN FALSE
       END IF
       I = I + 1
   WEND
   RETURN TRUE

END FUNCTION

' Test and display primes 1 .. 50 DIM n AS INTEGER

FOR n = 1 TO 50

   IF ISPRIME(n) THEN
       PRINT n, " ";
   END IF

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Press any key to continue...

Forth

<lang forth>: prime? ( n -- f )

       dup 2 < if      drop false
   else dup 2 = if      drop true
   else dup 1 and 0= if drop false
   else 3
       begin 2dup dup * >=
       while 2dup mod 0=
             if       2drop false exit
             then 2 +
       repeat         2drop true
   then then then ;</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran> FUNCTION isPrime(number)

  LOGICAL :: isPrime
  INTEGER, INTENT(IN) :: number
  INTEGER :: i

  IF(number==2) THEN
     isPrime = .TRUE.
  ELSE IF(number < 2 .OR. MOD(number,2) == 0) THEN
     isPRIME = .FALSE.
  ELSE
     isPrime = .TRUE.
     DO i = 3, INT(SQRT(REAL(number))), 2
        IF(MOD(number,i) == 0) THEN
           isPrime = .FALSE.
           EXIT
        END IF
     END DO
  END IF
END FUNCTION</lang>

F#

<lang fsharp>open NUnit.Framework open FsUnit

let isPrime x =

 match x with
 | 2 | 3 -> true
 | x when x % 2 = 0 -> false
 | _ ->
    let rec aux i =
       match i with
       | i when x % i = 0 -> false
       | i when x < i*i -> true
       | _ -> aux (i+2)
    aux 3

[<Test>] let ``Validate that 2 is prime`` () =

 isPrime 2 |> should equal true

[<Test>] let ``Validate that 4 is not prime`` () =

 isPrime 4 |> should equal false

[<Test>] let ``Validate that 3 is prime`` () =

 isPrime 3 |> should equal true

[<Test>] let ``Validate that 9 is not prime`` () =

 isPrime 9 |> should equal false

[<Test>] let ``Validate that 5 is prime`` () =

 isPrime 5 |> should equal true

[<Test>] let ``Validate that 277 is prime`` () =

 isPrime 277 |> should equal true</lang>

Shorter version using sequence and library function:

<lang fsharp> let isPrime x =

 if x < 2 then false else
 if x = 2 then true else
 if x % 2 = 0 then false else
 seq { 3 .. 2 .. int(sqrt (double x)) } |> Seq.forall (fun i -> x % i <> 0)</lang>

However, the sequence operations are quite slow and the following is faster using a recursive iteration:

<lang fsharp> let isPrime x =

 if x < 2 then false else
 if x = 2 then true else
 if x % 2 = 0 then false else
 let sr = int (sqrt (double x))
 let rec test n =
   if n > sr then true else
   if x % n = 0 then false else test (n + 2) in test 3

</lang>

and if you want to test really big numbers, use System.Numerics.BigInteger, but it's slower:

<lang fsharp> let isPrimeI x =

   if x < 2I then false else
   if x = 2I then true else
   if x % 2I = 0I then false else
   let rec test n =
     if n * n > x then true else
     if x % n = 0I then false else test (n + 2I) in test 3I

</lang>

If you have a lot of prime numbers to test, caching a sequence of primes can speed things up considerably, so you only have to do the divisions against prime numbers.

<lang fsharp> let rec primes = Seq.cache(Seq.append (seq[ 2; 3; 5 ]) (Seq.unfold (fun state -> Some(state, state + 2)) 7 |> Seq.filter (fun x -> IsPrime x)))

and IsPrime number =

   let rec IsPrimeCore number current limit =
       let cprime = primes |> Seq.nth current
       if cprime >= limit then
           true
       else if number % cprime = 0 then
           false
       else
           IsPrimeCore number (current + 1) (number/cprime)

   if number = 2 then
       true
   else if number < 2 then
       false
   else
       IsPrimeCore number 0 number

</lang>

GAP

<lang gap>IsPrimeTrial := function(n)

  local k, m;
  if n < 5 then
     return (n = 2) or (n = 3);
  fi;
  if RemInt(n, 2) = 0 then
     return false;
  fi;
  m := RootInt(n);
  k := 3;
  while k <= m do
     if RemInt(n, k) = 0 then
        return false;
     fi;
     k := k + 2;
  od;
  return true;

end;

Filtered([1 .. 100], IsPrimeTrial);

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]</lang>

Go

<lang go>func isPrime(p int) bool {

   if p < 2 { return false }
   if p == 2 { return true }
   if p % 2 == 0 { return false }

   for i := 3; i*i < p; i += 2 {
       if p % i == 0 { return false }
   }
   return true

}</lang>

Groovy

<lang groovy>def isPrime = {

   it == 2 || 
   it > 1 &&
   (2..Math.max(2, (int) Math.sqrt(it))).every{ k -> it % k != 0 }

}

(0..20).grep(isPrime)</lang>

Output:

[2, 3, 5, 7, 11, 13, 17, 19]

Haskell

The basic divisibility test by odd numbers: <lang haskell>isPrime n = n==2 || n>2 && all ((> 0).mod n) (2:[3,5..floor.sqrt(fromIntegral n+1)])</lang>

Testing by prime numbers only is faster. Primes list is saved for reuse. Precalculation of primes pays off if testing more than just a few numbers: <lang haskell>noDivsBy factors n = foldr (\f r-> f*f>n || (n `mod` f /= 0 && r)) True factors

-- primeNums = filter (noDivsBy [2..]) [2..] primeNums = 2 : 3 : filter (noDivsBy $ tail primeNums) [5,7..]

isPrime n = n > 1 && noDivsBy primeNums n</lang> Any increasing unbounded primes source can be used with the testing function noDivsBy to define isPrime function, say one from Sieve of Eratosthenes, or noDivsBy itself can be used to define primeNums as shown above, because it stops when the square root is reached.

Trial division can be used to produce short ranges of primes: <lang haskell>primesFromTo n m = filter isPrime [n..m]</lang> This code, when inlined, rearranged and optimized, leads to segmented "generate-and-test" sieve by trial division.

Sieve by trial division

Filtering of candidate numbers by prime at a time is a kind of sieving. One often sees a "naive" version presented as an unbounded sieve of Eratosthenes, similar to David Turner's 1975 SASL code, <lang haskell>primes = sieve [2..] where

  sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]</lang>

As is shown in Melissa O'Neill's "The Genuine Sieve of Eratosthenes", this is rather a sub-optimal trial division algorithm. Its complexity is quadratic in number of primes produced whereas that of optimal trial division is $O(n^{1.5}/(\log n)^{0.5})$ , and of true SoE it is $O(n\log n\log \log n)$ , in n primes produced.

The above can be written on one line as <lang haskell>import Data.List (nubBy)

primes = nubBy (\p x -> x `mod` p == 0) [2..]</lang> (The above works with the reference implementation of nubBy in Haskell 98, but does not work with current versions of GHC due to a bug.)

A similar version, using gcd instead of modulus, is: <lang haskell>import Data.List (nubBy)

primes = nubBy (((>1).).gcd) [2..]</lang>

Bounded sieve by trial division

Bounded formulation has normal trial division complexity, because it can stop early through an explicit guard: <lang haskell>primesTo m = 2 : sieve [3,5..m] where

  sieve (p:xs) | p*p > m   = p : xs
               | otherwise = p : sieve [x | x <- xs, x `mod` p /= 0]</lang>

Postponed sieve by trial division

To make it unbounded, the guard cannot be simply discarded, the firing up of a filter by a prime should be postponed until its square is seen amongst the candidates: <lang haskell>primesT = 2 : 3 : sieve [5,7..] 9 (tail primesT) where

  sieve (x:xs) q ps@(p:t) | x < q     = x : sieve xs q ps
                          | otherwise = sieve [x | x <- xs, x `mod` p /= 0] (head t^2) t</lang>

Segmented Generate and Test

Explicating the list of filters as a list of factors to test by on each segment between the consecutive squares of primes (so that no testing is done prematurely), and rearranging to avoid recalculations, leads to this code: <lang haskell>primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) 0 where

  sieve x q ps k = let fs = take k (tail primesST) in
     filter (\x-> all ((/=0).mod x) fs) [x,x+2..q-2]
     ++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang>

Runs at empirical $O(n^{1.4...})$ time complexity, in n primes produced. Can be used as a framework for unbounded segmented sieves, replacing divisibility testing with proper sieve of Eratosthenes, etc.

HicEst

<lang HicEst> DO n = 1, 1E6

    Euler = n^2 + n + 41
    IF( Prime(Euler) == 0 ) WRITE(Messagebox) Euler, ' is NOT prime for n =', n
  ENDDO                            ! e.g.    1681 = 40^2 + 40 + 41 is NOT prime

END

FUNCTION Prime(number)

  Prime = number == 2
  IF( (number > 2) * MOD(number,2) ) THEN
    DO i = 3, number^0.5, 2
      IF(MOD(number,i) == 0) THEN
        Prime = 0
        RETURN
      ENDIF
    ENDDO
    Prime = 1
  ENDIF

END</lang>

Icon and Unicon

Procedure shown without a main program. <lang Icon>procedure isprime(n) #: return n if prime (using trial division) or fail if not n = integer(n) | n < 2 then fail # ensure n is an integer greater than 1 every if 0 = (n % (2 to sqrt(n))) then fail return n end</lang>

J

Generally, this task should be accomplished in J using 1&p:. Here we take an approach that's more comparable with the other examples on this page.

<lang j>isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.'</lang>

Java

<lang java>public static boolean prime(long a){

  if(a == 2){
     return true;
  }else if(a <= 1 || a % 2 == 0){
     return false;
  }
  long max = (long)Math.sqrt(a);
  for(long n= 3; n <= max; n+= 2){
     if(a % n == 0){ return false; }
  }
  return true;

}</lang>

By Regular Expression

<lang java>public static boolean prime(int n) {

   return !new String(new char[n]).matches(".?|(..+?)\\1+");

}</lang>

JavaScript

<lang javascript>function isPrime(n) {

 if (n == 2) {
   return true;
 } else if ((n < 2) || (n % 2 == 0)) {
   return false;
 } else {
   for (var i = 3; i <= Math.sqrt(n); i += 2) {
     if (n % i == 0)
       return false;
   }
   return true;
 }

}</lang>

Joy

From here <lang joy>DEFINE prime ==

       2
       [ [dup * >] nullary  [rem 0 >] dip  and ]
       [ succ ]
       while
       dup * < .</lang>

jq

Example -- the command line is followed by alternating lines of input and output:

$ jq -f is_prime.jq -2 false 1 false 2 true 100 false

Note: if your jq does not have all, the following will suffice:

def all(generator; condition):
  reduce generator as $i (true; . and ($i|condition));

K

<lang K> isprime:{(x>1)&&/x!'2_!1+_sqrt x}

  &isprime'!100

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</lang>

Liberty BASIC

<lang lb>for n =1 to 50

 if prime( n) = 1 then print n; " is prime."

next n

wait

function prime( n)

 if n =2 then
   prime =1
 else
   if ( n <=1) or ( n mod 2 =0) then
       prime =0
   else
       prime =1
       for i = 3 to int( sqr( n)) step 2
           if ( n MOD i) =0 then prime = 0: exit function
       next i
   end if
 end if

end function

end</lang>

Logo

<lang logo>to prime? :n

  if :n < 2 [output "false]
  if :n = 2 [output "true]
  if equal? 0 modulo :n 2 [output "false]
  for [i 3 [sqrt :n] 2] [if equal? 0 modulo :n :i [output "false]]
  output "true

end</lang>

LSE64

<lang LSE64>over : 2 pick

2dup : over over
even? : 1 & 0 =

# trial n d yields "n d 0/1 false" or "n d+2 true"
trial : 2 +                 true
trial : 2dup % 0 =   then 0 false
trial : 2dup dup * < then 1 false
trial-loop : trial &repeat

# prime? n yields flag
prime? : 3 trial-loop >flag drop drop
prime? : dup even? then drop false
prime? : dup 2 =   then drop true
prime? : dup 2 <   then drop false</lang>

Lua

<lang Lua>function IsPrime( n )

   if n <= 1 or ( n ~= 2 and n % 2 == 0 ) then
       return false
   end

   for i = 3, math.sqrt(n), 2 do

if n % i == 0 then

 	    return false

end

end

   return true

end</lang>

M4

<lang M4>define(`testnext',

  `ifelse(eval($2*$2>$1),1,
     1,
     `ifelse(eval($1%$2==0),1,
        0,
        `testnext($1,eval($2+2))')')')

define(`isprime',

  `ifelse($1,2,
     1,
     `ifelse(eval($1<=1 || $1%2==0),1,
        0,
        `testnext($1,3)')')')

isprime(9) isprime(11)</lang>

Output:

0
1

Maple

This could be coded in myriad ways; here is one. <lang Maple> TrialDivision := proc( n :: integer )

       if n <= 1 then
               false
       elif n = 2 then
               true
       elif type( n, 'even' ) then
               false
       else
               for local i from 3 by 2 while i * i <= n do
                       if irem( n, i ) = 0 then
                               return false
                       end if
               end do;
               true
       end if

end proc: </lang> Using this to pick off the primes up to 30, we get: <lang Maple> > select( TrialDivision, [seq]( 1 .. 30 ) );

                 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

</lang> Here is a way to check that TrialDivision above agrees with Maple's built-in primality test (isprime). <lang Maple> > N := 10000: evalb( select( TrialDivision, [seq]( 1 .. N ) ) = select( isprime, [seq]( 1 .. N ) ) );

                                 true

</lang>

Mathematica

<lang mathematica>IsPrime[n_Integer] := Block[{},

 If[n <= 1, Return[False]];
 If[n == 2, Return[True]]; If[Mod[n, 2] == 0, Return[False]];
 For[k = 3, k <= Sqrt[n], k += 2, If[Mod[n, k] == 0, Return[False]]];
 Return[True]]</lang>

MATLAB

<lang MATLAB>function isPrime = primalityByTrialDivision(n)

   if n == 2
       isPrime = true;
       return
   elseif (mod(n,2) == 0) || (n <= 1)
       isPrime = false;
       return
   end
   
   %First n mod (3 to sqrt(n)) is taken. This will be a vector where the
   %first element is equal to n mod 3 and the last element is equal to n
   %mod sqrt(n). Then the all function is applied to that vector. If all
   %of the elements of this vector are non-zero (meaning n is prime) then
   %all() returns true. Otherwise, n is composite, so it returns false.
   %This return value is then assigned to the variable isPrime.
   isPrime = all(mod(n, (3:round(sqrt(n))) ));

end</lang>

Sample output:

<lang MATLAB>>> arrayfun(@primalityByTrialDivision,(1:14))

ans =

    0     1     1     0     1     0     1     0     0     0     1     0     1     0</lang>

Maxima

<lang Maxima>isprme(n):= catch(

 for k: 2 thru sqrt(n) do if mod(n, k)=0 then throw(false),
 true);

map(isprme, [2, 3, 4, 65, 100, 181, 901]); /* [true, true, false, false, false, true, false] */</lang>

МК-61/52

MUMPS

<lang MUMPS>ISPRIME(N)

QUIT:(N=2) 1
NEW I,TP
SET TP=+'$PIECE((N/2),".",2)
IF 'TP FOR I=3:2:(N**.5) SET TP=+'$PIECE((N/I),".",2) Q:TP
KILL I
QUIT 'TP</lang>

Usage (0 is false, nonzero is true):

USER>W $$ISPRIME^ROSETTA(2)
1
USER>W $$ISPRIME^ROSETTA(4)
0
USER>W $$ISPRIME^ROSETTA(7)
1
USER>W $$ISPRIME^ROSETTA(97)
1
USER>W $$ISPRIME^ROSETTA(99)
0

NetRexx

<lang NetRexx>/* NetRexx */

options replace format comments java crossref savelog symbols nobinary

parse arg nbr rangeBegin rangeEnd .

if nbr = | nbr = '.' then do

 if rangeBegin =  | rangeBegin = '.' then rangeBegin = 1
 if rangeEnd   =  | rangeEnd   = '.' then rangeEnd   = 100
 if rangeEnd > rangeBegin then direction = 1
                          else direction = -1

 say 'List of prime numbers from' rangeBegin 'to' rangeEnd':'
 primes = 
 loop nn = rangeBegin to rangeEnd by direction
   if isPrime(nn) then primes = primes nn
   end nn
   primes = primes.strip
   say '  'primes.changestr(' ', ',')
   say '  Total number of primes:' primes.words
 end

else do

 if isPrime(nbr) then say nbr.right(20) 'is prime'
                 else say nbr.right(20) 'is not prime'
 end

return

method isPrime(nbr = long) public static binary returns boolean

 ip = boolean

 select
   when nbr < 2 then do
     ip = isFalse
     end
   when '2 3 5 7'.wordpos(Rexx(nbr)) \= 0 then do
     -- crude shortcut ripped from the Rexx example
     ip = isTrue
     end
   when  nbr // 2 == 0 | nbr // 3 == 0 then do
     -- another shortcut permitted by the one above
     ip = isFalse
     end
   otherwise do
     nn = long
     nnStartTerm = long 3 -- a reasonable start term - nn <= 2 is never prime
     nnEndTerm = long Math.ceil(Math.sqrt(nbr)) -- a reasonable end term
     ip = isTrue -- prime the pump (pun intended)
     loop nn = nnStartTerm to nnEndTerm by 2
        -- Note: in Rexx and NetRexx "//" is the 'remainder of division operator' (which is not the same as modulo)
       if nbr // nn = 0 then do
         ip = isFalse
         leave nn
         end
       end nn
     end
   end

 return ip

method isTrue public static returns boolean

 return 1 == 1

method isFalse public static returns boolean

 return \isTrue</lang>

Output:

$ java -cp . RCPrimality 
List of prime numbers from 1 to 100:
  2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
  Total number of primes: 25

$ java -cp . RCPrimality 91
                  91 is not prime

$ java -cp . RCPrimality 101
                 101 is prime

$ java -cp . RCPrimality . . 25
List of prime numbers from 1 to 25:
  2,3,5,7,11,13,17,19,23
  Total number of primes: 9

$ java -cp . RCPrimality . 9900 10010
List of prime numbers from 9900 to 10010:
  9901,9907,9923,9929,9931,9941,9949,9967,9973,10007,10009
  Total number of primes: 11

$ java -cp . RCPrimality . -57 1
List of prime numbers from -57 to 1:
  
  Total number of primes: 0

$ java -cp . RCPrimality . 100 -57
List of prime numbers from 100 to -57:
  97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2
  Total number of primes: 25

Rexx version reimplemented in NetRexx

Translation of: REXX

<lang NetRexx>/* NetRexx */

options replace format comments java crossref savelog symbols nobinary

/*REXX program tests for primality using (kinda smartish) trial division*/

parse arg n . /*let user choose how many, maybe*/ if n== then n=10000 /*if not, then assume the default*/ p=0 /*a count of primes (so far). */

                                      /*I like Heinz's 57 varieties... */
 loop j=-57 to n                      /*start in the cellar and work up*/
 if \isprime(j) then iterate          /*if not prime, keep looking.    */
 p=p+1                                /*bump the jelly bean counter.   */
 if j.length>2 then iterate           /*only show two-digit primes.    */
 say j.right(20) 'is prime.'          /*Just blab about the wee primes.*/
 end

say say "there're" p "primes up to" n '(inclusive).' exit

/*-------------------------------------ISPRIME subroutine---------------*/ method isprime(x) public static returns boolean --isprime: procedure; arg x /*get the number in question*/ if '2 3 5 7'.wordpos(x)\==0 then return 1 /*is it a teacher's pet? */ if x<2 | x//2==0 | x//3==0 then return 0 /*weed out the riff-raff. */

                                           /*Note:   //  is modulus.   */
  loop j=5 by 6 until j*j>x                /*skips multiples of three. */
  if x//j==0 | x//(j+2)==0 then return 0   /*do a pair of divides (mod)*/
  end

return 1 /*I'm exhausted, it's prime!*/</lang>

Objeck

<lang objeck>function : IsPrime(n : Int) ~ Bool {

 if(n <= 1) {
   return false;
 };
 
 for(i := 2; i * i <= n; i += 1;) {           
   if(n % i = 0) {
     return false;
   };
 };
 
 return true;

}</lang>

OCaml

<lang ocaml>let is_prime n =

 if n = 2 then true
 else if n < 2 || n mod 2 = 0 then false
 else
   let rec loop k =
     if k * k > n then true
     else if n mod k = 0 then false
     else loop (k+2)
   in loop 3</lang>

Octave

This function works on vectors and matrix. <lang octave>function b = isthisprime(n)

 for r = 1:rows(n)
   for c = 1:columns(n)
     b(r,c) = false;
     if ( n(r,c) == 2 )

b(r,c) = true;

     elseif ( (n(r,c) < 2) || (mod(n(r,c),2) == 0) )

b(r,c) = false;

     else

b(r,c) = true; for i = 3:2:sqrt(n(r,c)) if ( mod(n(r,c), i) == 0 ) b(r,c) = false; break; endif endfor

     endif
   endfor
 endfor

endfunction

% as test, print prime numbers from 1 to 100 p = [1:100]; pv = isthisprime(p); disp(p( pv ));</lang>

PARI/GP

<lang parigp>trial(n)={

 if(n < 4, return(n > 1)); /* Handle negatives */
 forprime(p=2,sqrt(n),
   if(n%p == 0, return(0))
 );
 1

};</lang>

Pascal

Translation of: BASIC

<lang Pascal>program primes;

function prime(n: integer): boolean; var

 i: integer; max: real;

begin

 if n = 2 then
   prime := true
 else if (n <= 1) or (n mod 2 = 0) then
   prime := false
 else begin
   prime := true; i := 3; max := sqrt(n);
   while i <= max do begin
     if n mod i = 0 then begin
       prime := false; exit
     end;
     i := i + 2
   end
 end

end;

{ Test and display primes 0 .. 50 } var

 n: integer;

begin

 for n := 0 to 50 do
   if (prime(n)) then
     write(n, ' ');

end.</lang>

Output:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Perl

A more idiomatic solution than the RE-based version below: <lang perl>sub prime { my $n = shift || $_;

   $n % $_ or return for 2 .. sqrt $n;
   $n > 1

}

print join(', ' => grep prime, 1..100), "\n";</lang>

By Regular Expression

JAPH by Abigail 1999 [1] in conference slides 2000 [2] <lang perl>sub isprime {

 ('1' x shift) !~ /^1?$|^(11+?)\1+$/

}

A quick test

print join(', ', grep(isprime($_), 0..39)), "\n";</lang>

Perl 6

Works with: Rakudo Star version 2010.09

Here we use a "none" junction which will autothread through the %% "is divisible by" operator to assert that $i is not divisible by 2 or any of the odd numbers up to its square root. Read it just as you would English: "Integer $i is prime if it is greater than one and is divisible by none of 2, 3, whatever + 2, up to but not including whatever is greater than the square root of $i." <lang perl6>sub prime (Int $i --> Bool) {

   $i > 1 and $i %% none 2, 3, *+2 ...^ * >= sqrt $i;

}</lang> (No pun indented.)

This can easily be improved in two ways. First, we generate the primes so we only divide by those, instead of all odd numbers. Second, we memoize the result using the //= idiom of Perl, which does the right-hand calculation and assigns it only if the left side is undefined. We also try to avoid recalculating the square root each time. <lang perl6>my @primes := 2, 3, 5, -> $p { ($p+2, $p+4 ... &prime)[*-1] } ... *; my @isprime = False,False; # 0 and 1 are not prime by definition sub prime($i) { @isprime[$i] //= ($i %% none @primes ...^ * > $_ given $i.sqrt.floor) }</lang> Note the mutual dependency between the prime generator and the prime tester.

Testing: <lang perl6>say "$_ is{ "n't" x !prime($_) } prime." for 1 .. 100;</lang>

PHP

<lang php><?php function prime($a) {

 if (($a % 2 == 0 && $a != 2) || $a < 2)
   return false;
 $limit = sqrt($a);
 for ($i = 2; $i <= $limit; $i++)
   if ($a % $i == 0)
     return false;
 return true;

}

foreach (range(1, 100) as $x)

 if (prime($x)) echo "$x\n";

?></lang>

By Regular Expression

<lang php><?php function prime($a) {

 return !preg_match('/^1?$|^(11+?)\1+$/', str_repeat('1', $a));

} ?></lang>

PicoLisp

<lang PicoLisp>(de prime? (N)

  (or
     (= N 2)
     (and
        (> N 1)
        (bit? 1 N)
        (for (D 3  T  (+ D 2))
           (T (> D (sqrt N)) T)
           (T (=0 (% N D)) NIL) ) ) ) )</lang>

PL/I

<lang PL/I>is_prime: procedure (n) returns (bit(1));

  declare n fixed (15);
  declare i fixed (10);

  if n < 2 then return ('0'b);
  if n = 2 then return ('1'b);
  if mod(n, 2) = 0 then return ('0'b);

  do i = 3 to sqrt(n) by 2;
     if mod(n, i) = 0 then return ('0'b);
  end;
  return ('1'b);

end is_prime;</lang>

PowerShell

<lang powershell>function isPrime ($n) {

   if ($n -eq 1) {
       return $false
   } else {
       return (@(2..[Math]::Sqrt($n) | Where-Object { $n % $_ -eq 0 }).Length -eq 0)
   }

}</lang>

Prolog

The following predicate showcases Prolog's support for writing predicates suitable for both testing and generating. In this case, assuming the Prolog implemenation supports indefinitely large integers, prime(N) can be used to generate primes until memory is exhausted. <lang Prolog>prime(2). prime(N) :-

 between(3, inf, N),
 1 is N mod 2,             % odd
 M is floor(sqrt(N+1)),    % round-off paranoia 
 Max is (M-1) // 2,        % integer division
 forall( between(1, Max, I), N mod (2*I+1) > 0 ).

</lang> Example using SWI-Prolog:

?- time( (bagof( P, (prime(P), ((P > 100000, !, fail); true)), Bag),
       length(Bag,N),
       last(Bag,Last),
       writeln( (N,Last) ) )).

% 1,724,404 inferences, 1.072 CPU in 1.151 seconds (93% CPU, 1607873 Lips)
Bag = [2, 3, 5, 7, 11, 13, 17, 19, 23|...],
N = 9592,
Last = 99991.

?-  time( prime(99991) ).
% 165 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 1213235 Lips)
true.

?-

PureBasic

<lang PureBasic>Procedure.i IsPrime(n)

  Protected k

  If n = 2
     ProcedureReturn #True
  EndIf

  If n <= 1 Or n % 2 = 0
     ProcedureReturn #False
  EndIf
  
  For k = 3 To Int(Sqr(n)) Step 2
     If n % k = 0
        ProcedureReturn #False
     EndIf
  Next

  ProcedureReturn #True

EndProcedure</lang>

Python

The simplest primality test, using trial division:

Works with: Python version 2.5

<lang python>def prime(a):

   return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1)))</lang>

Another test. Exclude even numbers first: <lang python>def prime2(a):

   if a == 2: return True
   if a < 2 or a % 2 == 0: return False
   return not any(a % x == 0 for x in xrange(3, int(a**0.5) + 1, 2))</lang>

Yet another test. Exclude multiples of 2 and 3, see http://www.devx.com/vb2themax/Tip/19051:

Works with: Python version 2.4

<lang python>def prime3(a):

   if a < 2: return False
   if a == 2 or a == 3: return True # manually test 2 and 3   
   if a % 2 == 0 or a % 3 == 0: return False # exclude multiples of 2 and 3

   maxDivisor = a**0.5
   d, i = 5, 2
   while d <= maxDivisor:
       if a % d == 0: return False
       d += i 
       i = 6 - i # this modifies 2 into 4 and viceversa

   return True</lang>

By Regular Expression

Regular expression by "Abigail".
(An explanation is given in "The Story of the Regexp and the Primes"). <lang python>>>> import re >>> def isprime(n):

   return not re.match(r'^1?$|^(11+?)\1+$', '1' * n)

>>> # A quick test >>> [i for i in range(40) if isprime(i)] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]</lang>

Qi

<lang Qi>(define prime?-0

 K N -> true where (> (* K K) N)
 K N -> false where (= 0 (MOD N K))
 K N -> (prime?-0 (+ K 2) N))

(define prime?

 1 -> false
 2 -> true
 N -> false where (= 0 (MOD N 2))
 N -> (prime?-0 3 N))</lang>

R

<lang R>isPrime <- function(n) {

 if (n == 2) return(TRUE)
 if ( (n <= 1) || ( n %% 2 == 0 ) ) return(FALSE)
 for( i in 3:sqrt(n) ) {
   if ( n %% i == 0 ) return(FALSE)
 }
 TRUE

}</lang>

<lang R>print(lapply(1:100, isPrime))</lang>

Racket

<lang Racket>#lang racket

(define (prime? number)

 (cond ((not (positive? number)) #f)
       ((= 1 number) #f)
       ((even? number) (= 2 number))
       (else (for/and ((i (in-range 3 (ceiling (sqrt number)))))
               (not (zero? (remainder number i)))))))</lang>

REBOL

<lang REBOL>prime?: func [n] [

   case [
       n = 2 [ true  ]
       n <= 1 or (n // 2 = 0) [ false ]
       true [
           for i 3 round square-root n 2 [
               if n // i = 0 [ return false ]
           ]
           true
       ]
   ]

]</lang>

<lang REBOL>repeat i 100 [ print [i prime? i]]</lang>

REXX

compact version

This version uses a technique which increments by six for testing primality (up to the √n). <lang rexx>/*REXX program tests for primality using (kinda smartish) trial division*/ parse arg n . /*let user choose how many, maybe*/ if n== then n=10000 /*if not, then assume the default*/ p=0 /*a count of primes (so far). */

     do j=-57  to n                   /*start in the cellar and work up*/
     if \isprime(j)  then iterate     /*if not prime, keep looking.    */
     p=p+1                            /*bump the jelly bean counter.   */
     if j<99 then say right(j,20) 'is prime.'   /*Just show wee primes.*/
     end   /*j*/

say say "There are" p "primes up to" n '(inclusive).' exit /*stick a fork in it, we're done.*/

/*──────────────────────────────────ISPRIME subroutine──────────────────*/ isprime: procedure; parse arg x /*get the number in question*/ if \datatype(x,'W') then return 0 /*X not an integer? ¬prime.*/ if wordpos(x,'2 3 5 7')\==0 then return 1 /*is number a teacher's pet?*/ if x<2 | x//2==0 | x//3==0 then return 0 /*weed out the riff-raff. */

  do k=5  by  6  until k*k > x             /*skips odd multiples of 3. */
  if x//k==0 | x//(k+2)==0  then return 0  /*do a pair of divides (mod)*/
  end   /*k*/
                                           /*Note:   //  is modulus.   */

return 1 /*done dividing, it's prime.*/</lang> output when using the default input of 10000

                   2 is prime.
                   3 is prime.
                   5 is prime.
                   7 is prime.
                  11 is prime.
                  13 is prime.
                  17 is prime.
                  19 is prime.
                  23 is prime.
                  29 is prime.
                  31 is prime.
                  37 is prime.
                  41 is prime.
                  43 is prime.
                  47 is prime.
                  53 is prime.
                  59 is prime.
                  61 is prime.
                  67 is prime.
                  71 is prime.
                  73 is prime.
                  79 is prime.
                  83 is prime.
                  89 is prime.
                  97 is prime.

there're 1229 primes up to 10000 (inclusive).

optimized version

This version separates multiple-clause IF statements, and also test for low primes,
making it about 8% faster. <lang rexx>/*REXX program tests for primality using (kinda smartish) trial division*/ parse arg n . /*let user choose how many, maybe*/ if n== then n=10000 /*if not, then assume the default*/ p=0 /*a count of primes (so far). */

     do j=-57  to n                   /*start in the cellar and work up*/
     if \isprime(j)  then iterate     /*if not prime, then keep looking*/
     p=p+1                            /*bump the jelly bean counter.   */
     if j<99 then say right(j,20) 'is prime.'   /*Just show wee primes.*/
     end   /*j*/

say; say "There are" p "primes up to" n '(inclusive).' exit /*stick a fork in it, we're done.*/

/*──────────────────────────────────ISPRIME subroutine──────────────────*/ isprime: procedure; parse arg x /*get integer to be investigated.*/ if \datatype(x,'W') then return 0 /*X isn't an integer? Not prime.*/ if x<11 then return wordpos(x,'2 3 5 7')\==0 /*is it a wee prime? */ if x//2==0 then return 0 /*eliminate the evens. */ if x//3==0 then return 0 /* ··· and eliminate the triples.*/

                                      /*right dig test: faster than //.*/
  do k=5  by 6  until k*k > x         /*this skips odd multiples of 3. */
  if x // k     == 0   then return 0  /*perform a divide (modulus),    */
  if x // (k+2) == 0   then return 0  /* ··· and the next umpty one.   */
  end   /*k*/
                                      /*Note:      //     is modulus.  */

return 1 /*did all divisions, it's prime. *//</lang> output is identical to the first version.

unrolled version

This version uses an unrolled version (of the 2^nd version) of some multiple-clause IF statements, and
also an optimized version of the testing of low primes, making it about 22% faster.

Note that the DO ... UNTIL ... was changed to DO ... WHILE .... <lang rexx>/*REXX program tests for primality using (kinda smartish) trial division*/ parse arg n . /*let user choose how many, maybe*/ if n== then n=10000 /*if not, then assume the default*/ p=0 /*a count of primes (so far). */

     do j=-57  to n                   /*start in the cellar and work up*/
     if \isprime(j)  then iterate     /*if not prime, then keep looking*/
     p=p+1                            /*bump the jelly bean counter.   */
     if j<99 then say right(j,20) 'is prime.'   /*Just show wee primes.*/
     end   /*j*/

say; say "There are" p "primes up to" n '(inclusive).' exit /*stick a fork in it, we're done.*/

/*──────────────────────────────────ISPRIME subroutine──────────────────*/ isprime: procedure; parse arg x /*get integer to be investigated.*/ if \datatype(x,'W') then return 0 /*X isn't an integer? Not prime.*/ if x<107 then do /*test for (low) special cases. */

             _='2 3 5 7 11 13 17 19 23 29 31 37 41 43 47', /*list of ··*/
               '53 59 61 67 71 73 79 83 89 97 101 103'     /*wee primes*/
             return wordpos(x,_)\==0   /*is it a wee prime? ··· or not?*/
             end

if x// 2 ==0 then return 0 /*eliminate the evens. */ if x// 3 ==0 then return 0 /* ··· and eliminate the triples.*/ if right(x,1) == 5 then return 0 /* ··· and eliminate the nickels.*/ if x// 7 ==0 then return 0 /* ··· and eliminate the luckies.*/ if x//11 ==0 then return 0 if x//13 ==0 then return 0 if x//17 ==0 then return 0 if x//19 ==0 then return 0 if x//23 ==0 then return 0 if x//29 ==0 then return 0 if x//31 ==0 then return 0 if x//37 ==0 then return 0 if x//41 ==0 then return 0 if x//43 ==0 then return 0 if x//47 ==0 then return 0 if x//53 ==0 then return 0 if x//59 ==0 then return 0 if x//61 ==0 then return 0 if x//67 ==0 then return 0 if x//71 ==0 then return 0 if x//73 ==0 then return 0 if x//79 ==0 then return 0 if x//83 ==0 then return 0 if x//89 ==0 then return 0 if x//97 ==0 then return 0 if x//101==0 then return 0 if x//103==0 then return 0

                                      /*Note:      //     is modulus.  */
  do k=107  by 6  while k*k<=x        /*this skips odd multiples of 3. */
  if x // k     == 0   then return 0  /*perform a divide (modulus),    */
  if x // (k+2) == 0   then return 0  /* ··· and the next umpty one.   */
  end   /*k*/

return 1 /*after all that, ··· it's prime.*/</lang> output is identical to the first version.

Ruby

<lang ruby>def prime(a)

 if a == 2
   true
 elsif a <= 1 || a % 2 == 0
   false
 else
   divisors = Enumerable::Enumerator.new(3..Math.sqrt(a), :step, 2)
   # this also creates an enumerable object:  divisors = (3..Math.sqrt(a)).step(2)
   !divisors.any? { |d| a % d == 0 }
 end

end</lang> The mathn package in the stdlib for Ruby 1.9.2 contains this compact Prime#prime? method: <lang ruby> def prime?(value, generator = Prime::Generator23.new)

   return false if value < 2
   for num in generator
     q,r = value.divmod num
     return true if q < num
     return false if r == 0
   end
 end</lang>

Without any fancy stuff: <lang ruby>def primes(limit)

 (enclose = lambda { |primes| 
   primes.last.succ.upto(limit) do |trial_pri|
     if primes.find { |pri| (trial_pri % pri).zero? }.nil?
       return enclose.call(primes << trial_pri)
     end
   end
   primes
 }).call([2])

end</lang>

By Regular Expression

<lang ruby>def isprime(n)

 '1'*n !~ /^1?$|^(11+?)\1+$/

end</lang>

Run BASIC

<lang runbasic>' Test and display primes 1 .. 50 for i = 1 TO 50

 if prime(i) <> 0 then print i;" ";

next i

FUNCTION prime(n) if n < 2 then prime = 0 : goto [exit] if n = 2 then prime = 1 : goto [exit] if n mod 2 = 0 then prime = 0 : goto [exit] prime = 1 for i = 3 to int(n^.5) step 2

if n mod i = 0 then  prime = 0 : goto [exit]

next i [exit]

END FUNCTION</lang>

2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49

SAS

<lang sas>data primes; do n=1 to 1000;

 link primep;
 if primep then output;

end; stop;

primep: if n < 4 then do;

 primep=n=2 or n=3;
 return;

end; primep=0; if mod(n,2)=0 then return; do k=3 to sqrt(n) by 2;

 if mod(n,k)=0 then return;

end; primep=1; return; keep n; run;</lang>

Scala

Simple version, robustified

<lang Scala> def isPrime(n: Int) = {

   assume(n <= Int.MaxValue - 1)
   n > 1 && (Iterator.from(2) takeWhile (d => d * d <= n) forall (n % _ != 0))
 }</lang>

Optimized version FP and parallel runabled

<lang Scala> def isPrime(n: Long) = {

   n > 1 && ((n % 2 != 0) || (n == 2)) && ((3 until Math.sqrt(n).toInt by 2).par forall (n % _ != 0))
 }

 assert(isPrime(9223372036854775783L)) // Biggest 63-bit prime
 assert(!isPrime(Long.MaxValue))</lang>

Optimized version FP, robustified and tail recursion

<lang Scala> def isPrime(n: Int) = {

   @tailrec
   def inner(n: Int, k: Int): Boolean = {
     if (k * k > n) true
     else if (n % k != 0) inner(n, k + 2) else false
   }

   assume(n <= Int.MaxValue - 1)
   n > 1 && ((n % 2 != 0) || (n == 2)) && inner(n, 3)

}</lang>

Output:

The testcases for all the Scala versions above

<lang Scala> assert(isPrime(2))

 assert(!isPrime(9))
 assert(isPrime(214748357))
 assert(!isPrime(Int.MaxValue - 1))</lang>

Scheme

Works with: Scheme version R

^{5}

RS

<lang scheme>(define (prime? number)

 (define (*prime? divisor)
   (or (> (* divisor divisor) number)
       (and (> (modulo number divisor) 0)
            (*prime? (+ divisor 1)))))
 (and (> number 1)
      (*prime? 2)))</lang>

<lang scheme>; twice faster, testing only odd divisors (define (prime? n)

 (if (< n 4) (> n 1)
     (and (odd? n)

(let loop ((k 3)) (or (> (* k k) n) (and (positive? (remainder n k)) (loop (+ k 2))))))))</lang>

Seed7

<lang seed7>const func boolean: is_prime (in integer: number) is func

 result
   var boolean: prime is FALSE;
 local
   var integer: upTo is 0;
   var integer: testNum is 3;
 begin
   if number = 2 then
     prime := TRUE;
   elsif number rem 2 = 0 or number <= 1 then
     prime := FALSE;
   else
     upTo := sqrt(number);
     while number rem testNum <> 0 and testNum <= upTo do
       testNum +:= 2;
     end while;
     prime := testNum > upTo;
   end if;
 end func;</lang>

Original source: [3]

SNOBOL4

<lang SNOBOL4>define('isprime(n)i,max') :(isprime_end) isprime isprime = n

       le(n,1) :s(freturn)
       eq(n,2) :s(return)
       eq(remdr(n,2),0) :s(freturn)
       max = sqrt(n); i = 1

isp1 i = le(i + 2,max) i + 2 :f(return)

       eq(remdr(n,i),0) :s(freturn)f(isp1)

isprime_end</lang>

By Patterns

Using the Abigail regex transated to Snobol patterns. <lang SNOBOL4> define('rprime(n)str,pat1,pat2,m1') :(end_rprime) rprime str = dupl('1',n); rprime = n

       pat1 = ('1' | )
       pat2 = ('11' arbno('1')) $ m1 (*m1 arbno(*m1))
       str pos(0) (pat1 | pat2) rpos(0) :s(freturn)f(return)

end_rprime

# Test and display primes 0 .. 50

loop rprimes = rprimes rprime(n) ' '

       n = lt(n,50) n + 1 :s(loop)
       output = rprimes

end</lang>

Output:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

SQL

Works with: T-SQL

<lang tsql> declare @number int set @number = 514229 -- number to check

with cte(number) as

(

select 2
union all
select number+1
from cte
where number+1 < @number

) select

     cast(@number as varchar(100)) +
     case 
         when exists

( select * from ( select number, @number % number modNumber from cte ) tmp where tmp.modNumber = 0 ) then ' is composite' else ' is prime' end primalityTest option (maxrecursion 0) </lang>

Standard ML

<lang sml>fun is_prime n =

 if n = 2 then true
 else if n < 2 orelse n mod 2 = 0 then false
 else let
   fun loop k =
     if k * k > n then true
     else if n mod k = 0 then false
     else loop (k+2)
   in loop 3
 end</lang>

Tcl

<lang tcl>proc is_prime n {

   if {$n <= 1} {return false}
   if {$n == 2} {return true}
   if {$n % 2 == 0} {return false}
   for {set i 3} {$i <= sqrt($n)} {incr i 2} {
       if {$n % $i == 0} {return false}
   }
   return true

}</lang>

TI-83 BASIC

Prompt A
If A=2:Then
Disp "PRIME"
Stop
End

If (fPart(A/2)=0 and A>0) or A<2:Then
Disp "NOT PRIME"
Stop
End

1→P
For(B,3,int(√(A)))
If FPart(A/B)=0:Then
0→P
√(A)→B
End
B+1→B
End

If P=1:Then
Disp "PRIME"
Else
Disp "NOT PRIME"
End

UNIX Shell

Translation of: C

Works with: bash

Works with: ksh93

Works with: pdksh

Works with: zsh

<lang bash>function primep { typeset n=$1 p=3 (( n == 2 )) && return 0 # 2 is prime. (( n & 1 )) || return 1 # Other evens are not prime. (( n >= 3 )) || return 1

# Loop for odd p from 3 to sqrt(n). # Comparing p * p <= n can overflow. while (( p <= n / p )); do # If p divides n, then n is not prime. (( n % p )) || return 1 (( p += 2 )) done return 0 # Yes, n is prime. }</lang>

Works with: Bourne Shell

<lang bash>primep() { set -- "$1" 3 test "$1" -eq 2 && return 0 # 2 is prime. expr "$1" \% 2 >/dev/null || return 1 # Other evens are not prime. test "$1" -ge 3 || return 1

# Loop for odd p from 3 to sqrt(n). # Comparing p * p <= n can overflow. We use p <= n / p. while expr $2 \<= "$1" / $2 >/dev/null; do # If p divides n, then n is not prime. expr "$1" % $2 >/dev/null || return 1 set -- "$1" `expr $2 + 2` done return 0 # Yes, n is prime. }</lang>

Ursala

Excludes even numbers, and loops only up to the approximate square root or until a factor is found. <lang Ursala>#import std

import nat

prime = ~<{0,1}&& -={2,3}!| ~&h&& (all remainder)^Dtt/~& iota@K31</lang> Test program to try it on a few numbers: <lang Ursala>#cast %bL

test = prime* <5,6,7></lang>

Output:

<true,false,true>

V

Translation of: Joy

<lang v>[prime?

    2
    [[dup * >] [true] [false] ifte [% 0 >] dip and]
      [succ]
    while
    dup * <].</lang>

Using it:

<lang v>|11 prime? =true |4 prime? =false</lang>

XPL0

<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations

func Prime(N); \Return 'true' if N is a prime number int N; int I; [if N <= 1 then return false; for I:= 3 to sqrt(N) do

       if rem(N/I) = 0 then return false;

return true; ]; \Prime

int Num; repeat Num:= IntIn(0);

       Text(0, if Prime(Num) then "is " else "not ");
       Text(0, "prime^M^J");

until Num = 0</lang>

Example output:

777777777
not prime
777777773
is prime
0
not prime

zkl

The Method filter1 stops at the first non False result, which, if there is one, is the first found diviser, thus short cutting the rest of the test <lang zkl>fcn isPrime(n){

  if(n.isEven or n<2) return(n==2); 
  (not [3..n.toFloat().sqrt().toInt(),2].filter1('wrap(m){n%m==0}))

}</lang>

Output:

zkl: [1..].filter(20,isPrime)
L(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71)
zkl: isPrime(777777773)
True
zkl: isPrime(777777777)
False