Primality by trial division: Difference between revisions
(→{{header|Haskell}}: simplify code) |
(* Related task: Sieve of Eratosthenes. SoE says this is its related task, so add it here as well.) |
||
Line 2: | Line 2: | ||
Use trial division. Even numbers may be eliminated right away. A loop from 3 to √(n) will suffice, but other loops are allowed. |
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]]. |
|||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
Revision as of 22:04, 9 September 2011
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.
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>#include <math.h>
- define FALSE 0
- define TRUE 1
int isPrime( unsigned int n ) {
unsigned int i; if ( n == 2 ) return TRUE; if ( n <= 1 || ( n & 1 ) == 0 ) return FALSE; for ( i = 3 ; i <= sqrt( n ) ; i += 2 ) if ( n % i == 0 ) return FALSE; return TRUE;
}</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.
(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))))))
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, testing by primes only instead of by odds: <lang haskell>primeNums = 2 : [n | n <- [3,5..], isPrime n]
isPrime n = n > 1 && foldr (\p r-> p*p>n || (rem n p /= 0 && r)) True primeNums</lang>
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 http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-imper.html <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>
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
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
- 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
- R
- REBOL
- REXX
- Ruby
- Scala
- Scheme
- Seed7
- SNOBOL4
- Standard ML
- Tcl
- TI-83 BASIC
- Ursala
- V