Primality by trial division: Difference between revisions
m Sorry for too many minor edits... n00b |
restore page after destructive C++ edit |
||
Line 154:
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>
=={{header|E}}==
{{trans|D}}
<lang e>
def isPrime(n :int) {
if (n == 2) {
return true
} else if (n <= 1 || n %% 2 == 0) {
return false
} else {
def limit := (n :float64).sqrt().ceil()
var divisor := 1
while ((divisor += 2) <= limit) {
if (n %% divisor == 0) {
return false
}
}
return true
}
}</lang>
=={{header|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>
=={{header|FALSE}}==
[0\$2=$[@~@@]?~[$$2>\1&&[\~\
3[\$@$@1+\$*>][\$@$@$@$@\/*=[%\~\$]?2+]#%
]?]?%]p:
=={{header|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 ;
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<lang fortran> FUNCTION isPrime(number)
LOGICAL :: isPrime
INTEGER, INTENT(IN) :: number
INTEGER :: i
IF(number==2) THEN
isPrime = .TRUE.
ELSE IF(number < 2 .OR. MOD(number,2) == 0) THEN
isPRIME = .FALSE.
ELSE
isPrime = .TRUE.
DO i = 3, INT(SQRT(REAL(number))), 2
IF(MOD(number,i) == 0) THEN
isPrime = .FALSE.
EXIT
END IF
END DO
END IF
END FUNCTION</lang>
=={{header|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:
<pre>[2, 3, 5, 7, 11, 13, 17, 19]</pre>
=={{header|Haskell}}==
Without square roots:
divides k 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..])
=={{header|J}}==
{{eff note|J|1&p:}}
<lang j>isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.'</lang>
=={{header|Java}}==
<lang java>public static boolean prime(long a){
if(a == 2){
return true;
}else if(a <= 1 || a % 2 == 0){
return false;
}
for(long n= 3; n <= (long)Math.sqrt(a); 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>
=={{header|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>
=={{header|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
=={{header|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
=={{header|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:
<pre>
0
1
</pre>
=={{header|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
)
=={{header|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>
=={{header|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>
=={{header|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===
{{trans|Python}}
<lang perl>sub isprime {
('1' x shift) !~ /^1?$|^(11+?)\1+$/
}
# A quick test
print join(', ', grep(isprime($_), 0..39)), "\n";</lang>
=={{header|Perl 6}}==
{{works with|Rakudo|#22 "Thousand Oaks"}}
Most simply:
<lang perl6>sub prime (Int $n) { $n > 1 and $n !% none 2 .. sqrt $n }</lang>
Skipping even numbers when possible:
<lang perl6>sub prime (Int $n where (* > 0)) returns Bool {
when $n == 1 { False }
when $n == 2|3 { True }
when $n < 25 { $n % 2 and $n % 3 }
default { $n !% none 2, 3 ... * + 2, sqrt $n }
}</lang>
Testing:
<lang perl6>say "$_ is{ prime($_) ?? '' !! 'n\'t' } prime." for 1 .. 100;</lang>
=={{header|PHP}}==
<lang php><?php
function prime($a) {
if ($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>
=={{header|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>
<!-- Yes, I got a little carried away with the pipeline. This function checks whether the number of divisors between 2 and √n is zero and in that case it's a prime. -->
=={{header|PureBasic}}==
{{Works with |PureBasic| 4.41}}
<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>
=={{header|Python}}==
The simplest primality test, using trial division:
{{works with|Python|2.5}}
<lang python>def prime(a):
return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1)))</lang>
Another test. Exclude even numbers first:
<lang python>def prime2(a):
if a == 2: return True
if a < 2 or a % 2 == 0: return False
return not any(a % x == 0 for x in xrange(3, int(a**0.5) + 1, 2))</lang>
Yet another test. Exclude multiples of 2 and 3, see http://www.devx.com/vb2themax/Tip/19051:
{{works with|Python|2.4}}
<lang python>def prime3(a):
if a < 2: return False
if a == 2 or a == 3: return True # manually test 2 and 3
if a % 2 == 0 or a % 3 == 0: return False # exclude multiples of 2 and 3
maxDivisor = a**0.5
d, i = 5, 2
while d <= maxDivisor:
if a % d == 0: return False
d += i
i = 6 - i # this modifies 2 into 4 and viceversa
return True</lang>
===By Regular Expression===
Regular expression by "Abigail".<br>
(An explanation is given in "[http://paddy3118.blogspot.com/2009/08/story-of-regexp-and-primes.html 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>
=={{header|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>
=={{header|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>
=={{header|Scheme}}==
<lang scheme>(define (is-prime? x)
(cond ((< x 2) #f)
((= x 2) #t)
((zero? (remainder x 2)) #f)
(else
(let loop ((c 3))
(cond ((> (* c c) x) #t)
((zero? (remainder x c)) #f)
(else (loop (+ c 2))))))))</lang>
=={{header|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>
=={{header|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>
=={{header|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
=={{header|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:
<pre>
<true,false,true>
</pre>
=={{header|V}}==
like joy
[prime?
2
[[dup * >] [true] [false] ifte [% 0 >] dip and]
[succ]
while
dup * <].
Using it
|11 prime?
=true
|4 prime?
=false
|
Revision as of 17:33, 8 March 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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.
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
<lang algol68>main:(</lang>
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> 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: <lang algol68>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</lang>
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)}'
BASIC
Going with the classic 1 for "true" and 0 for "false":
FUNCTION prime% (n!) IF n = 2 THEN prime = 1 IF n <= 1 OR n MOD 2 = 0 THEN prime = 0 FOR a = 3 TO INT(SQR(n)) STEP 2 IF n MOD a = 0 THEN prime = 0 NEXT a prime = 1 END FUNCTION
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>
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>
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>
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>
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
Without square roots:
divides k 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..])
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; } for(long n= 3; n <= (long)Math.sqrt(a); 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>
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>
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
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
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 )
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>
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
<lang perl>sub isprime {
('1' x shift) !~ /^1?$|^(11+?)\1+$/
}
- A quick test
print join(', ', grep(isprime($_), 0..39)), "\n";</lang>
Perl 6
Most simply:
<lang perl6>sub prime (Int $n) { $n > 1 and $n !% none 2 .. sqrt $n }</lang>
Skipping even numbers when possible:
<lang perl6>sub prime (Int $n where (* > 0)) returns Bool {
when $n == 1 { False } when $n == 2|3 { True } when $n < 25 { $n % 2 and $n % 3 } default { $n !% none 2, 3 ... * + 2, sqrt $n }
}</lang>
Testing:
<lang perl6>say "$_ is{ prime($_) ?? !! 'n\'t' } prime." for 1 .. 100;</lang>
PHP
<lang php><?php function prime($a) {
if ($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>
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>
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>
Scheme
<lang scheme>(define (is-prime? x)
(cond ((< x 2) #f) ((= x 2) #t) ((zero? (remainder x 2)) #f) (else (let loop ((c 3)) (cond ((> (* c c) x) #t) ((zero? (remainder x c)) #f) (else (loop (+ c 2))))))))</lang>
Standard ML
<lang sml>fun is_prime n =
if n = 2 then true else if n < 2 orelse n mod 2 = 0 then false else let fun loop k = if k * k > n then true else if n mod k = 0 then false else loop (k+2) in loop 3 end</lang>
Tcl
<lang tcl>proc is_prime n {
if {$n <= 1} {return false} if {$n == 2} {return true} if {$n % 2 == 0} {return false} for {set i 3} {$i <= sqrt($n)} {incr i 2} { if {$n % $i == 0} {return false} } return true
}</lang>
TI-83 BASIC
Prompt A If A=2:Then Disp "PRIME" Stop End If (fPart(A/2)=0 and A>0) or A<2:Then Disp "NOT PRIME" Stop End 1→P For(B,3,int(√(A))) If FPart(A/B)=0:Then 0→P √(A)→B End B+1→B End If P=1:Then Disp "PRIME" Else Disp "NOT PRIME" End
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