Primality by trial division

From Rosetta Code

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.

Contents 1 ActionScript 2 Ada 3 ALGOL 68 4 AutoHotkey 5 AWK 6 BASIC 7 C 8 C++ 9 Clojure 10 Common Lisp 11 D 11.1 Version with excluded multiplies of 2 and 3 12 E 13 Factor 14 FALSE 15 Forth 16 Fortran 17 Groovy 18 Haskell 19 J 20 Java 20.1 By Regular Expression 21 Joy 22 Logo 23 LSE64 24 M4 25 MAXScript 26 OCaml 27 Octave 28 Perl 28.1 By Regular Expression 29 Perl 6 30 PHP 30.1 By Regular Expression 31 PowerShell 32 PureBasic 33 Python 33.1 By Regular Expression 34 R 35 Ruby 35.1 By Regular Expression 36 Scheme 37 Standard ML 38 Tcl 39 TI-83 BASIC 40 Ursala 41 V

[edit] ActionScript

function isPrime(n:int):Boolean
{
	if(n < 2) return false;
	if(n == 2) return true;
	if((n & 1) == 0) return false;
	for(var i:int = 3; i <= Math.sqrt(n); i+= 2)
		if(n % i == 0) return false;
	return true;
}

[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:(

COMMENT
  This routine is used in more than one place, and is essentially a
  template that can by used for many different types, eg INT, LONG INT...
USAGE
  MODE ISPRIMEINT = INT, LONG INT, etc
  PR READ "prelude/is_prime.a68" PR
END COMMENT

PROC is prime = ( ISPRIMEINT p )BOOL:
  IF p <= 1 OR ( NOT ODD p AND p/= 2) THEN
    FALSE
  ELSE
    BOOL prime := TRUE;
    FOR i FROM 3 BY 2 TO ENTIER sqrt(p)
      WHILE prime := p 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] AutoHotkey

Discussion

MsgBox % IsPrime(1995937) 
Loop 
   MsgBox % A_Index-3 . " is " . (IsPrime(A_Index-3) ? "" : "not ") . "prime." 
 
IsPrime(n,k=2) { ; testing primality with trial divisors not multiple of 2,3,5, up to sqrt(n) 
   d := k+(k<7 ? 1+(k>2) : SubStr("6-----4---2-4---2-4---6-----2",Mod(k,30),1)) 
   Return n < 3 ? n>1 : Mod(n,k) ? (d*d <= n ? IsPrime(n,d) : 1) : 0 
}

[edit] AWK

$ awk 'func prime(n){for(d=2;d<=sqrt(n);d++)if(!(n%d)){return 0};return 1}{print prime($1)}'

[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] C++

#include <cmath>
 
bool is_prime(unsigned int n)
{
    if (n <= 1)
        return false;
    if (n == 2)
        return true;
    for (unsigned int i = 2; i <= sqrt(n); ++i)
        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
     (empty? (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)))
 

 
(defun primep (n)
  "Is N prime?"
  (and (> n 1) 
       (or (= n 2) (oddp n))
       (loop for i from 3 to (isqrt n) by 2
	  never (zerop (rem n i)))))
 

[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] E

Translation of: D

 
def isPrime(n :int) {
    if (n == 2) {
        return true
    } else if (n <= 1 || n %% 2 == 0) {
        return false
    } else {
        def limit := (n :float64).sqrt().ceil()
        var divisor := 1
        while ((divisor += 2) <= limit) {
            if (n %% divisor == 0) {
                return false
            }
        }
        return true
    }
}

[edit] Factor

USING: combinators kernel math math.functions math.ranges sequences ;
 
: prime? ( n -- ? )
    {
        { [ dup 2 < ] [ drop f ] }
        { [ dup even? ] [ 2 = ] }
        [ 3 over sqrt 2 <range> [ mod 0 > ] with all? ]
    } cond ;

[edit] FALSE

[0\$2=$[@~@@]?~[$$2>\1&&[\~\
  3[\$@$@1+\$*>][\$@$@$@$@\/*=[%\~\$]?2+]#%
]?]?%]p:

[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] Groovy

def isPrime = {
    it == 2 || 
    it > 1 &&
    (2..Math.max(2, (int) Math.sqrt(it))).every{ k -> it % k != 0 }
}
 
(0..20).grep(isPrime)

Sample output:

[2, 3, 5, 7, 11, 13, 17, 19]

[edit] Haskell

Without square roots:

divides k n = n `mod` k == 0

isPrime :: Integer -> Bool
isPrime n | n < 2     = False
          | otherwise = not $ any (`divides` n) $ takeWhile (\k -> k*k <= n) (2:[3,5..])

[edit] J

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

[edit] 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;
}

[edit] By Regular Expression

public static boolean prime(int n) {
    return !new String(new char[n]).matches(".?|(..+?)\\1+");
}

[edit] Joy

From http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-imper.html

 
DEFINE prime ==
        2
        [ [dup * >] nullary  [rem 0 >] dip  and ]
        [ succ ]
        while
        dup * < .
 

[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] M4

 
define(`testnext',
   `ifelse(eval($2*$2>$1),1,
      1,
      `ifelse(eval($1%$2==0),1,
         0,
         `testnext($1,eval($2+2))')')')
define(`isprime',
   `ifelse($1,2,
      1,
      `ifelse(eval($1<=1 || $1%2==0),1,
         0,
         `testnext($1,3)')')')
 
isprime(9)
isprime(11)
 

Output:

0
1

[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 (k+2)
    in loop 3

[edit] Octave

This function works on vectors and matrix.

function b = isthisprime(n)
  for r = 1:rows(n)
    for c = 1:columns(n)
      b(r,c) = false;
      if ( n(r,c) == 2 )
	b(r,c) = true;
      elseif ( (n(r,c) < 2) || (mod(n(r,c),2) == 0) )
	b(r,c) = false;
      else
	b(r,c) = true;
	for i = 3:2:sqrt(n(r,c))
	  if ( mod(n(r,c), i) == 0 )
	    b(r,c) = false;
	    break;
	  endif
	endfor
      endif
    endfor
  endfor
endfunction
 
% as test, print prime numbers from 1 to 100
p = [1:100];
pv = isthisprime(p);
disp(p( pv ));

[edit] Perl

A more idiomatic solution:

sub prime { my $n = shift || $_;
    $n % $_ or return for 2 .. sqrt $n;
    $n > 1
}
 
print join(', ' => grep prime, 1..100), "\n";

[edit] By Regular Expression

Translation of: Python

sub isprime {
  ('1' x shift) !~ /^1?$|^(11+?)\1+$/
}
 
# A quick test
print join(', ', grep(isprime($_), 0..39)), "\n";

[edit] Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

Most simply:

sub prime (Int $n) { $n > 1 and $n !% none 2 .. sqrt $n }

Skipping even numbers when possible:

sub prime (Int $n where (* > 0)) returns Bool {
    when    $n == 1   { False }
    when    $n == 2|3 { True }
    when    $n < 25   { $n % 2 and $n % 3 }
    default           { $n !% none 2, 3 ... * + 2, sqrt $n }
}

Testing:

say "$_ is{ prime($_) ?? '' !! 'n\'t' } prime." for 1 .. 100;

[edit] PHP

<?php
function prime($a) {
  if ($a < 2)
    return false;
  $limit = sqrt($a);
  for ($i = 2; $i <= $limit; $i++)
    if ($a % $i == 0)
      return false;
  return true;
}
 
foreach (range(1, 100) as $x)
  if (prime($x)) echo "$x\n";
 
?>

[edit] By Regular Expression

<?php
function prime($a) {
  return !preg_match('/^1?$|^(11+?)\1+$/', str_repeat('1', $a));
}
?>

[edit] PowerShell

function isPrime ($n) {
    if ($n -eq 1) {
        return $false
    } else {
        return (@(2..[Math]::Sqrt($n) | Where-Object { $n % $_ -eq 0 }).Length -eq 0)
    }
}

[edit] PureBasic

Works with: PureBasic version 4.41

Procedure.i IsPrime(n)
   Protected k
 
   If n = 2
      ProcedureReturn #True
   EndIf   
 
   If n <= 1 Or n % 2 = 0
      ProcedureReturn #False
   EndIf
 
   For k = 3 To Int(Sqr(n)) Step 2
      If n % k = 0
         ProcedureReturn #False
      EndIf
   Next
 
   ProcedureReturn #True
EndProcedure

[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 xrange(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 xrange(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] By Regular Expression

Regular expression by "Abigail".
(An explanation is given in "The Story of the Regexp and the Primes").

>>> import re
>>> def isprime(n):
    return not re.match(r'^1?$|^(11+?)\1+$', '1' * n)
 
>>> # A quick test
>>> [i for i in range(40) if isprime(i)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
 

[edit] R

isPrime <- function(n) {
  if (n == 2) return(TRUE)
  if ( (n <= 1) || ( n %% 2 == 0 ) ) return(FALSE)
  for( i in 3:sqrt(n) ) {
    if ( n %% i == 0 ) return(FALSE)
  }
  TRUE
}

print(lapply(1:100, isPrime))

[edit] Ruby

def prime(a)
  if a == 2
    true
  elsif a <= 1 || a % 2 == 0
    false
  else
    divisors = Enumerable::Enumerator.new(3..Math.sqrt(a), :step, 2)
    # this also creates an enumerable object:  divisors = (3..Math.sqrt(a)).step(2)
    !divisors.any? { |d| a % d == 0 }
  end
end

The mathn package in the stdlib for Ruby 1.9.2 contains this compact Prime#prime? method:

  def prime?(value, generator = Prime::Generator23.new)
    return false if value < 2
    for num in generator
      q,r = value.divmod num
      return true if q < num
      return false if r == 0
    end
  end

Without any fancy stuff:

def primes(limit)
  (enclose = lambda { |primes| 
    primes.last.succ.upto(limit) do |trial_pri|
      if primes.find { |pri| (trial_pri % pri).zero? }.nil?
        return enclose.call(primes << trial_pri)
      end
    end
    primes
  }).call([2])
end

[edit] By Regular Expression

def isprime(n)
  '1'*n !~ /^1?$|^(11+?)\1+$/
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] Standard ML

fun is_prime n =
  if n = 2 then true
  else if n < 2 orelse n mod 2 = 0 then false
  else let
    fun loop k =
      if k * k > n then true
      else if n mod k = 0 then false
      else loop (k+2)
    in loop 3
  end

[edit] Tcl

proc is_prime n {
    if {$n <= 1} {return false}
    if {$n == 2} {return true}
    if {$n % 2 == 0} {return false}
    for {set i 3} {$i <= sqrt($n)} {incr i 2} {
        if {$n % $i == 0} {return false}
    }
    return true
}

[edit] TI-83 BASIC

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,int(√(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

[edit] Ursala

excludes even numbers, and loops only up to the approximate square root or until a factor is found

 
#import std
#import nat
 
prime = ~<{0,1}&& -={2,3}!| ~&h&& (all remainder)^Dtt/~& iota@K31
 

test program to try it on a few numbers:

 
#cast %bL
 
test = prime* <5,6,7>
 

output:

<true,false,true>

[edit] V

like joy

[prime?
    2
    [[dup * >] [true] [false] ifte [% 0 >] dip and]
      [succ]
    while
    dup * <].

Using it

|11 prime?
=true
|4 prime?
=false