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.
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;
BASIC
Compiler: QuickBasic 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
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; }
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)))
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; }
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 ;
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..]
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.'
Java
public static boolean prime(double a){ if(a == 2){ return true; }else if(a <= 1 || a % 2 == 0){ return false; } for(double n= 3; n <= (long)Math.sqrt(a); n+= 2){ if(a % n == 0){ return false; } } return true; }
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
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 )
Python
The simplest primality test, using trial division:
Interpreter: Python 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:
Interpreter: Python 2.5
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:
Interpreter: Python 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
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
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+1→B End If P=1:Then Disp "PRIME" Else Disp "NOT PRIME" End