Primality by trial division
Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime.
![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.
Implement the simplest primality test, using trial division.
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++
bool is_prime(unsigned number) { // directly check for small numbers if (number < 11) { switch(number) { case 2: case 3: case 5: case 7: return true; default: return false; } } else { // quickly check for most common cases switch (number % 30) { default: return false; case 1: case 7: case 11: case 13: case 17: case 19: case 23: case 29: // OK, we might have a prime. // We already have caught all multiples of 2, 3 and 5, so we can start testing at 7. // We would only have to check for primes, but first checking each numer if it's a prime // would be too expensive. But we can easily exclude multiples of 2, 3 and 5. // the array diff contains the steps to go forward (starting from 7; so the first step is // 4, to go from 7 to 11). The steps are periodic; when we get to the end of the array, // we have to continue at the beginning unsigned diff[8] = { 4, 2, 4, 2, 4, 6, 2, 6 }; for(unsigned den=7, pos = 0; den*den <= number; den += diff[pos], pos = (pos+1) % 8) { // if we can divide without remainder, it's not a prime if (number % den == 0) return false; } // if we get here, we have a prime 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..]
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; }
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
def prime(a): if a < 2: return False else: return not any([a % x == 0 for x in range(2, min(ceil(a**0.5)+1,a))])
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