Primality by trial division

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.

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..]

J

Actually 1&p: would do, but the task calls for trial division, so:

isprime1=: 3 : 0
 if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.
)

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

The simplest primality test, using trial division:

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:

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: sqrt

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,sqrt(A))
If FPart(A/B)=0:Then
0->P
sqrt(A)->B
End
B+1->B
End

If P=1:Then
Disp "PRIME"
Else
Disp "NOT PRIME"
End