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 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.
ActionScript
<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
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>
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
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!
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>
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>
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
<lang d>import std.math: sqrt; bool isPrime(int n) {
if (n == 2)
return true;
if (n <= 1 || (n & 1) == 0)
return false;
for(int i = 3; i <= sqrt(cast(float)n); i += 2)
if (n % i == 0)
return false;
return true;
}</lang>
Version with excluded multiplies of 2 and 3
<lang d>/**
* to compile: * $ dmd -run prime_trial.d * to optimize: * $ dmd -O -inline -release prime_trial.d */
module prime_trial;
import std.conv : to; import std.stdio : writefln;
/// Adapted from: http://www.devx.com/vb2themax/Tip/19051 bool isprime(Integer)(in Integer number) {
/* 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
}
/// print all prime numbers less then a given limit void main(char[][] args) {
const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
for (uint i = 0; i < limit; ++i)
if (isprime(i))
writefln(i);
}</lang>
Two way test
Odd divisors is generated both from increasing and decreasing sequence, may improve performance for numbers that have large minimum factor. <lang d>bool isprime(T)(T n) {
if(n % 2 == 0 || n <= 1) return n == 2 ;
T head = 3, tail = (cast(T)sqrt(n) /2)*2 + 1;
for(; head <= tail ; head +=2, tail -= 2)
if((n % head) == 0 || (n % tail) == 0 )
return false ;
return true ;
}</lang>
Delphi
<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>
E
<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>
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>
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
[0\$2=$[@~@@]?~[$$2>\1&&[\~\ 3[\$@$@1+\$*>][\$@$@$@$@\/*=[%\~\$]?2+]#% ]?]?%]p:
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
<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>
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 == 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>
Sample output:
[2, 3, 5, 7, 11, 13, 17, 19]
Haskell
<lang haskell>k `divides` n = n `mod` k == 0
isPrime :: Integer -> Bool isPrime n
| n < 2 = False | otherwise = not . any (`divides` n) $ takeWhile (\k -> k*k <= n) (2:[3,5..])</lang>
Faster code, also testing by primes only instead of by odds: <lang haskell>isPrime n = primeQ primeNums n
primeQ primes n = n > 1 && foldr (\p r-> p*p>n || (rem n p /= 0 && r)) True primes
primeNums = 2 : [n | n <- [3,5..], primeQ primeNums n]</lang>
Any unbounded primes source (as well as, less efficiently, odds prefixed with 2) can be used with the testing function primeQ to define isPrime, say one from Sieve of Eratosthenes, or primeQ itself can be used to define primes list corecursively as e.g. primeNums above, because it stops as soon as the square root is reached.
Trial division can be used to quickly produce short ranges of primes: <lang haskell>primesFromTo n m = takeWhile (<= m) $ filter isPrime [n..]</lang>
The code for primeNums, when inlined, rearranged and optimized, leads to segmented "generate-and-test" sieve by trial division.
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
<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.ceil(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>
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
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
<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
Mathematica
<lang>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]
]</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 me 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>
MAXScript
<lang 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
)
</lang>
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
<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
<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: <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
Here we use a "none" junction which will autothread through the %% "is divisible by" operator to assert that $n is not divisible by 2 or any of the odd numbers up to its square root. Read it just as you would English: "Integer $n 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 $n."
<lang perl6>sub prime (Int $n --> Bool) {
$n > 1 and $n %% none 2, 3, *+2 ...^ * > sqrt $n;
}</lang>
(No pun indented.)
Testing: <lang>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>
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>
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:
<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:
<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>
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
<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). */
/*I like Heinz's 57 varieties... */ 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 length(j)>2 then iterate /*only show two-digit primes. */ say right(j,20) 'is prime.' /*Just blab about the wee primes.*/ end
say say "there're" p "primes up to" n '(inclusive).' exit
/*─────────────────────────────────────ISPRIME subroutine───────────────*/
isprime: procedure; arg x /*get the number in question*/
if wordpos(x,'2 3 5 7')\==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. */ do 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> Output when using the defdault input:
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).
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>
Scala
<lang scala>def isPrime(n: Int) = n > 1 && (Iterator.from(2) takeWhile (d => d * d <= n) forall (n % _ != 0))</lang>
Scheme
<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>
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
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
<lang bash>primep() { local 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>
<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
like joy
[prime?
2
[[dup * >] [true] [false] ifte [% 0 >] dip and]
[succ]
while
dup * <].
Using it
|11 prime? =true |4 prime? =false
- Programming Tasks
- Prime Numbers
- ActionScript
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- ZX Spectrum Basic
- C
- C++
- C sharp
- Clojure
- CMake
- Common Lisp
- D
- Delphi
- E
- Erlang
- Factor
- FALSE
- Forth
- Fortran
- GAP
- Go
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- J
- Java
- JavaScript
- Joy
- Liberty BASIC
- Logo
- LSE64
- Lua
- M4
- Mathematica
- MATLAB
- MAXScript
- MUMPS
- NetRexx
- Objeck
- OCaml
- Octave
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PowerShell
- PureBasic
- Python
- Qi
- R
- REBOL
- REXX
- Ruby
- Scala
- Scheme
- Seed7
- SNOBOL4
- Standard ML
- Tcl
- TI-83 BASIC
- UNIX Shell
- Ursala
- V