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.
Primality by trial division
You are encouraged to solve this task according to the task description, using any language you may know.
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