Primality by trial division

Primality by trial division
You are encouraged to solve this task according to the task description, using any language you may know.

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 task: Sieve of Eratosthenes, Prime decomposition.

ACL2

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

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

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;

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

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

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

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 
}

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

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

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

BASIC

Works with: QuickBasic version 4.5

Returns 1 for prime, 0 for non-prime

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

Output:

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

ZX Spectrum Basic

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 
 

Output:

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

BBC BASIC

      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

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

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

Output:

100000000003
100000000019
100000000057
100000000063
100000000069
100000000073
100000000091

Burlesque

 
fcL[2==
 

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

Version not using the fc function:

 
blsq ) 11^^2\/?dr@.%{0==}ayn!
1
blsq ) 12^^2\/?dr@.%{0==}ayn!
0
blsq ) 13^^2\/?dr@.%{0==}ayn!
1
 

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

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

C++

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

C#

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

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.

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

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)

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

COBOL

Works with: OpenCOBOL

       >>source format is free
identification division.
program-id. prime-div.
 
data division.
working-storage section.
 
*> The number for which we are testing primality.
01 num     pic 9(6) value 1.
01 out-num pic z(6).
 
*> Division-related stuff.
01 div     pic 9(6).
01 div-lim pic 9(6).
01 rem     pic 9(6).
    88 not-prime value 0.
 
procedure division.
main.
    perform until num = 0
        perform get-a-num
        perform is-prime
        move num to out-num
        if not-prime
            display out-num " is not prime."
        else
            display out-num " is prime."
        end-if
    end-perform
 
    stop run
    .
 
is-prime.
    if num = 1
        move 0 to rem
    else if num < 4
        move 1 to rem
    else
        compute div-lim = function sqrt(num) + 1
        perform with test after varying div from 2 by 1
                until (div = div-lim) or not-prime
            compute rem = function mod(num, div)
        end-perform
    end-if
    .
 
get-a-num.
    display "Enter a possible prime number (0 to stop): " with no advancing
    accept num
    if num = 0
        stop run
    end-if
    .

Example:

Enter a possible prime number (0 to stop): 2
     2 is prime.
Enter a possible prime number (0 to stop): 3
     3 is prime.
Enter a possible prime number (0 to stop): 4
     4 is not prime.
Enter a possible prime number (0 to stop): 5
     5 is prime.
Enter a possible prime number (0 to stop): 65537
 65537 is prime.
Enter a possible prime number (0 to stop): 0

External function

This example was written by a novice in COBOL. If you are familiar with COBOL, please review and edit this example and remove this message. If the example does not work and you cannot fix it, replace this message with {{incorrect|COBOL|description of problem as you see it}}. If the code is correct but unidiomatic and you cannot fix it, replace this message with {{improve|COBOL|description of how it should be improved}}.

OpenCOBOL with separately compiled source files.

Main program:

 
Identification division.
Program-id. prime-by-div-main.
 
Data division.
Working-storage section.
01 num-out pic z(10).
01 num pic 9(10).
01 ans pic x.
    88 is-prime value "y".
 
Procedure division.
Main.
Perform until 1 = 2 
    display "Number: " with no advancing
    accept num
    move num to num-out
    if num = 0 stop run end-if
    call "prime-by-div-subr" using num by reference ans
    if ans = "Y" display num-out " is prime."
    else display num-out " is not prime."   
end-perform.
Stop run.
 

Subroutine for determining primality.

 
Identification division.
Program-id. prime-by-div-subr.
 
Data division.
Working-storage section.
01 div pic 9(10).
01 lim pic 9(10).
01 rem pic 9(10).
    88 is-not-prime value 0.
 
Linkage section.
01 the-num pic 9(10).
01 the-ans pic x.
 
Procedure division using the-num, the-ans.
Main.
Move "Y" to the-ans.
If the-num < 4 exit program.
Compute lim = Function sqrt(the-num) + 1.
Perform
    with test after
    varying div from 2 by 1
    until div > lim or is-not-prime
    compute rem = function mod(the-num, div)
end-perform.
If is-not-prime move "N" to the-ans.
Exit program.
 

Example output:

Number: 1
         1 is prime.
Number: 2
         2 is prime.
Number: 3
         3 is prime.
Number: 4
         4 is not prime.
Number: 5
         5 is prime.
Number: 6
         6 is not prime.
Number: 7
         7 is prime.
Number: 8
         8 is not prime.
Number: 32769
     32769 is not prime.
Number: 65537
     65537 is prime.
Number: 0

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

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

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

D

Simple Version

import std.stdio, std.algorithm, std.range, std.math;
 
bool isPrime(in int n) pure nothrow {
    if ((n & 1) == 0 || n <= 1)
        return n == 2;
 
    for(int i = 3; i <= sqrt(cast(real)n); i += 2)
        if (n % i == 0)
            return false;
    return true;
}
 
void main() { // demo code
    iota(2, 40).filter!isPrime().writeln();
}

Output:

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

Version with excluded multiplies of 2 and 3

Same output.

import std.stdio, std.algorithm, std.range;
 
bool isPrime2(Integer)(in Integer number) pure nothrow {
  // Adapted from: http://www.devx.com/vb2themax/Tip/19051
  // manually test 1, 2, 3 and multiples of 2 and 3
  if (number == 2 || number == 3)
    return true;
  else if (number < 2 || number % 2 == 0 || number % 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 number */
  for (Integer divisor = 5, increment = 2; divisor*divisor <= number;
       divisor += increment, increment = 6 - increment)
    if (number % divisor == 0)
      return false;
 
  return true; // if we get here, the number is prime
}
 
void main() { // demo code
    iota(2, 40).filter!isPrime2().writeln();
}

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.

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)sqrt(cast(real)n) / 2) * 2 + 1;
    for ( ; head <= tail ; head +=2, tail -= 2)
        if ((n % head) == 0 || (n % tail) == 0)
            return false;
    return true;
}
 
void main() { // demo code
    iota(2, 40).filter!isPrime3().writeln();
}

Delphi

First

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;

Second

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;

E

Translation of: D

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

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

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

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 ;

FALSE

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

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.

#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
NEXT
 
PAUSE
 

Output

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

Forth

: prime? ( n -- ? )
        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 ;

Fortran

Works with: Fortran version 90 and later

 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

F#

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

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 ]

Go

func isPrime(p int) bool {
    if p < 2 {return false}
    if p % 2 == 0 { return false }
 
    for i := 3; i*i < p; i += 2 {
        if p % i == 0 { return false }
    }
    return true
}

Groovy

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

Output:

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

Haskell

The basic divisibility test by odd numbers:

isPrime n = n==2 || n>2 && all ((> 0).rem n) (2:[3,5..floor.sqrt(fromIntegral n+1)])

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:

noDivsBy factors n = foldr (\f r-> f*f>n || (rem n 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

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:

primesFromTo n m = filter isPrime [n..m]

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,

primes = sieve [2..] where
   sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]

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 / (logn)^0.5), and of true SoE it is O(nlognloglogn), in n primes produced.

Bounded sieve by trial division

Bounded formulation has normal trial division complexity, because it can stop early through an explicit guard:

primesTo m = 2 : sieve [3,5..m] where
   sieve (p:xs) | p*p > m   = p : xs
                | otherwise = p : sieve [x | x <- xs, rem x p /= 0]

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:

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, rem x p /= 0] (head t^2) t

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:

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).rem x) fs) [x,x+2..q-2]
      ++ sieve (q+2) (head ps^2) (tail ps) (k+1)

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

   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

Icon and Unicon

Procedure shown without a main program.

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

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.

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

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

By Regular Expression

public static boolean prime(int n) {
    return !new String(new char[n]).matches(".?|(..+?)\\1+");
}

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

Joy

From here

DEFINE prime ==
        2
        [ [dup * >] nullary  [rem 0 >] dip  and ]
        [ succ ]
        while
        dup * < .

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

Liberty BASIC

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

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

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

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

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)

Output:

0
1

Maple

This could be coded in myriad ways; here is one.

 
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:
 

Using this to pick off the primes up to 30, we get:

 
> select( TrialDivision, [seq]( 1 .. 30 ) );
                  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
 

Here is a way to check that TrialDivision above agrees with Maple's built-in primality test (isprime).

 
> N := 10000: evalb( select( TrialDivision, [seq]( 1 .. N ) ) = select( isprime, [seq]( 1 .. N ) ) );
                                  true
 

Mathematica

IsPrime[n_Integer] :=
 Module[{k = 2},
  If[n <= 1, Return False];
  If[n == 2, Return True];
  While[k <= Sqrt[n],
   If[Mod[n, k] == 0, Return[False], k++]
   ];
  Return[True]
 ]

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

Sample output:

>> arrayfun(@primalityByTrialDivision,(1:14))
 
ans =
 
     0     1     1     0     1     0     1     0     0     0     1     0     1     0

MAXScript

 fn isPrime n =
 (
     if n == 2 then
     (
         return true
     )
     else if (n <= 1) OR (mod n 2 == 0) then
     (
         return false
     )
 
     for i in 3 to (sqrt n) by 2 do
     (
         if mod n i == 0 then return false
     )
     true
 )

МК-61/52

П0	2	-	x#0	29	ИП0	2	/	{x}	x#0
31	3	П4	ИП0	КвКор	ИП4	-	x>=0	29	ИП0
ИП4	/	{x}	x#0	31	КИП4	КИП4	БП	13	1
С/П	0	С/П

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

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

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

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

/* 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!*/

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

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

Octave

This function works on vectors and matrix.

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

PARI/GP

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

Pascal

Translation of: BASIC

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.

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:

sub prime { my $n = shift || $_;
    $n % $_ or return for 2 .. sqrt $n;
    $n > 1
}
 
print join(', ' => grep prime, 1..100), "\n";

By Regular Expression

JAPH by Abigail 1999 [1] in conference slides 2000 [2]

sub isprime {
  ('1' x shift) !~ /^1?$|^(11+?)\1+$/
}
 
# A quick test
print join(', ', grep(isprime($_), 0..39)), "\n";

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

sub prime (Int $i --> Bool) {
    $i > 1 and $i %% none 2, 3, *+2 ...^ * >= sqrt $i;
}

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

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

Note the mutual dependency between the prime generator and the prime tester.

Testing:

say "$_ is{ "n't" x !prime($_) } prime." for 1 .. 100;

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";
 
?>

By Regular Expression

<?php
function prime($a) {
  return !preg_match('/^1?$|^(11+?)\1+$/', str_repeat('1', $a));
}
?>

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

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;

PowerShell

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

Prolog

prime(2).
prime(N) :- integer(N), N > 1,
    M is floor(sqrt(N+1)),    % round-off paranoia 
    N mod 2 > 0,              % is odd
    check_by_odds(N, M, 3).
 
check_by_odds(N, M, S) :-
    M2 is (M-1) // 2, S2 is S // 2,
    forall( between(S2,M2,X), N mod (2*X+1) > 0 ).
 
/*
check_by_odds(N, M, F) :- F > M.
check_by_odds(N, M, F) :- F =< M,
    N mod F > 0,
    F1 is F + 2,              % test by odds only
    check_by_odds(N, M, F1).*/ 

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

Python

The simplest primality test, using trial division:

Works with: Python version 2.5

def prime(a):
    return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1)))

Another test. Exclude even numbers first:

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

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

Works with: Python version 2.4

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

By Regular Expression

Regular expression by "Abigail".
(An explanation is given in "The Story of the Regexp and the Primes").

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

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

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
}

print(lapply(1:100, isPrime))

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

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

repeat i 100 [ print [i prime? i]]

REXX

compact version

This version uses a technique which increments by six for testing primality (up to the √n).

/*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.*/

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.

/*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. *//

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

/*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.*/

output is identical to the first version.

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

The mathn package in the stdlib for Ruby 1.9.2 contains this compact Prime#prime? method:

  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

Without any fancy stuff:

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

By Regular Expression

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

Run BASIC

' 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

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

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;

Scala

def isPrime(n: Int) = n > 1 && (Iterator.from(2) takeWhile (d => d * d <= n) forall (n % _ != 0))

Scheme

Works with: Scheme version R⁵RS

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

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

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;

Original source: [3]

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

By Patterns

Using the Abigail regex transated to Snobol patterns.

        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

Output:

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

SQL

Works with: T-SQL

 
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)
 

Standard ML

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

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
}

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

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

Works with: Bourne Shell

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

Ursala

Excludes even numbers, and loops only up to the approximate square root or until a factor is found.

#import std
#import nat
 
prime = ~<{0,1}&& -={2,3}!| ~&h&& (all remainder)^Dtt/~& iota@K31

Test program to try it on a few numbers:

#cast %bL
 
test = prime* <5,6,7>

Output:

<true,false,true>

V

Translation of: Joy

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

Using it:

|11 prime?
=true
|4 prime?
=false

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

Example output:

777777777
not prime
777777773
is prime
0
not prime