Primality by Trial Division
From Rosetta Code
Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.
Use trial division. Even numbers may be eliminated right away. A loop from 3 to √(n) will suffice, but other loops are allowed.
Contents |
[edit] 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;
[edit] ALGOL 68
main:(
PROC is prime = ( INT n )BOOL:
(
IF n = 2 THEN
TRUE
ELIF n <= 1 OR n MOD 2 = 0 THEN
FALSE
ELSE
BOOL prime := TRUE;
FOR i FROM 3 BY 2 TO ENTIER sqrt(n) WHILE prime := n MOD i /= 0 DO
SKIP
OD;
prime
FI
);
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
[edit] BASIC
Works with: QuickBasic version 4.5
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
[edit] 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; }
[edit] 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
(nil? (filter #(divides % n) (take-while #(< (* % %) n) (range 2 n))))))
[edit] 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)))
[edit] 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; }
[edit] Version with excluded multiplies of 2 and 3
/** * 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); }
[edit] 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 ;
[edit] 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
[edit] Haskell
Without square roots:
divides k n = n `mod` k == 0 isPrime :: Integer -> Bool isPrime n | n < 2 = False isPrime n = not $ any (`divides` n) $ takeWhile (\k -> k*k <= n) [2..]
[edit] J
Actually 1&p: would do, but the task calls for trial division, so:
isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.'
[edit] Joy
From http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-imper.html
prime ==
2
[ [dup * >] nullary [rem 0 >] dip and ]
[ succ ]
while
dup * < ;
[edit] Java
public static boolean prime(double 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; }
[edit] 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
[edit] 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
[edit] 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
)
[edit] 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 (succ k) in loop 3
[edit] Perl
sub prime { $a = shift; if ($a == 2) { return 1; } if ($a <= 1 || $a % 2 == 0) { return 0; } $d = 3; while ($d <= sqrt($a)) { if ($a % $d == 0) { return 0; } $d += 2; } return 1; }
[edit] 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 range(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 range(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
[edit] Ruby
def prime(a) if a==2 return true end if a<=1 || a%2==0 return false end d=3 while d <= Math.sqrt(a) do if a%d==0 return false end d+=2 end return true end
[edit] 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))))))))
[edit] TI-83 BASIC
Calculator symbol translations:
"STO" arrow: →
Square root sign: √
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,√(A)) If FPart(A/B)=0:Then 0→P √(A)→B End B+2→B End If P=1:Then Disp "PRIME" Else Disp "NOT PRIME" End
[edit] V
like joy
[prime?
2
[[dup * >] [true] [false] ifte [% 0 >] dip and]
[succ]
while
dup * <].
Using it
|11 prime? =true |4 prime? =false
Categories: Less Than 20 Examples | Programming Tasks | Prime Numbers | Ada | ALGOL 68 | BASIC | C | Clojure | Common Lisp | D | Forth | Fortran | Haskell | J | Joy | Java | Logo | LSE64 | MAXScript | OCaml | Perl | Python | Ruby | Scheme | TI-83 BASIC | V
