Primality by trial division: Difference between revisions

From Rosetta Code
Content added Content deleted
(Add Seed7 example)
(Add link to original source)
Line 1,104: Line 1,104:
end if;
end if;
end func;</lang>
end func;</lang>

Original source: [http://seed7.sourceforge.net/algorith/math.htm#is_prime]


=={{header|SNOBOL4}}==
=={{header|SNOBOL4}}==

Revision as of 07:52, 7 September 2011

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

ActionScript

<lang 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; }</lang>

Ada

<lang 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;</lang>

ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
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

<lang algol68>main:( 

 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$)

)</lang> 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

AutoHotkey

Discussion <lang autohotkey>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

}</lang>

AWK

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

Or more legibly, and with n <= 1 handling

<lang AWK>function prime(n) { 

   if (n <= 1) return 0
   for (d = 2; d <= sqrt(n); d++)
       if (!(n % d)) return 0
   return 1

}

{print prime($1)}</lang>

BASIC

Works with: QuickBasic version 4.5

Returns 1 for prime, 0 for non-prime

<lang QBasic>FUNCTION prime% (n!) 

 STATIC i AS INTEGER
 IF n = 2 THEN
   prime = 1
 ELSEIF n <= 1 OR n MOD 2 = 0 THEN
   prime = 0
 ELSE
   prime = 1
   FOR i = 3 TO INT(SQR(n)) STEP 2
     IF n MOD i = 0 THEN
       prime = 0
       EXIT FUNCTION
     END IF
   NEXT i
 END IF

END FUNCTION

' Test and display primes 1 .. 50 DECLARE FUNCTION prime% (n!) FOR n = 1 TO 50 

 IF prime(n) = 1 THEN PRINT n;

NEXT n</lang>

Output: 

 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47

ZX Spectrum Basic

<lang ZXBasic>10 LET n=0: LET p=0 20 INPUT "Enter number: ";n 30 GO SUB 1000 40 IF p=0 THEN PRINT n;" is not prime!" 50 IF p<>0 THEN PRINT n;" is prime!" 60 GO TO 10 1000 REM *************** 1001 REM * PRIME CHECK * 1002 REM *************** 1010 LET p=0 1020 IF n/2=INT (n/2) THEN RETURN 1030 LET p=1 1040 FOR i=3 TO SQR (n) STEP 2 1050 IF n/i=INT (n/i) THEN LET p=0: LET i= SQR (n) 1060 NEXT i 1070 RETURN </lang> Output: 

15 is not prime!
17 is prime!
119 is not prime!
137 is prime!

C

<lang c>#include <math.h>

  1. define FALSE 0
  2. 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;

}</lang>

C++

<lang cpp>#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;

}</lang>

C#

<lang csharp>static bool isPrime(int n) 

       {
           if (n <= 1) return false;
           for (int i = 2; i * i <= n; i++)            
               if (n % i == 0) return false;            
           return true;
       }</lang>

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))))))

Common Lisp

<lang 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)))

</lang> <lang Lisp> (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))))) </lang>

D

<lang 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;

}</lang>

Version with excluded multiplies of 2 and 3

<lang d>/** 

* 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);

}</lang>

Two way test

Odd divisors is generated both from increasing and decreasing sequence, may improve performance for numbers that have large minimum factor. <lang d>bool isprime(T)(T n) { 

   if(n % 2 == 0 || n <= 1) return n == 2 ;
   T head = 3, tail = (cast(T)sqrt(n) /2)*2 + 1;
   for(; head <= tail ; head +=2, tail -= 2)
       if((n % head) == 0 || (n % tail) == 0 )
           return false ;
   return true ;

}</lang>

Delphi

<lang Delphi> function IsPrime(aNumber: Integer): Boolean; var 

 I: Integer;

begin 

 Result:= True;
 if(aNumber = 2) then Exit;

 Result:= not ((aNumber mod 2 = 0)  or
               (aNumber <= 1));
 if not Result then Exit;

 for I:=3 to Trunc(Sqrt(aNumber)) do
 if(aNumber mod I = 0) then
 begin
   Result:= False;
   Break;
 end;

end; </lang>

E

Translation of: D

<lang e> 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
   }

}</lang>

Erlang

<lang erlang>is_prime(N) when N == 2 -> true; is_prime(N) when N < 2 orelse N rem 2 == 0 -> false; is_prime(N) -> is_prime(N,3).

is_prime(N,K) when K*K > N -> true; is_prime(N,K) when N rem K == 0 -> false; is_prime(N,K) -> is_prime(N,K+2). </lang>

Factor

<lang 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 ;</lang>

FALSE

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

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 ;

Fortran

Works with: Fortran version 90 and later

<lang fortran> 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</lang>

GAP

<lang gap>IsPrimeTrial := function(n) 

  local k, m;
  if n < 5 then
     return (n = 2) or (n = 3);
  fi;
  if RemInt(n, 2) = 0 then
     return false;
  fi;
  m := RootInt(n);
  k := 3;
  while k <= m do
     if RemInt(n, k) = 0 then
        return false;
     fi;
     k := k + 2;
  od;
  return true;

end;

Filtered([1 .. 100], IsPrimeTrial);

  1. [ 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 ]</lang>

Go

<lang go> func isPrime(p int) bool { 

   if p < 2 {return false}
   if p % 2 == 0 { return false }

   for i := 3; i*i < p; i += 2 {
       if p % i == 0 { return false }
   }
   return true

} </lang>

Groovy

<lang groovy>def isPrime = { 

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

}

(0..20).grep(isPrime)</lang>

Sample output: 

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

Haskell

<lang haskell>k `divides` 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..])</lang>

Faster code, testing by primes only instead of by odds: <lang haskell>primeNums = 2 : [n | n <- [3,5..], isPrime n]

isPrime n 

   | n<2  = False
   | True = foldr (\p r-> p*p>n || (rem n p /= 0 && r)) True primeNums</lang>

HicEst

<lang HicEst> DO n = 1, 1E6 

    Euler = n^2 + n + 41
    IF( Prime(Euler) == 0 ) WRITE(Messagebox) Euler, ' is NOT prime for n =', n
  ENDDO                            ! e.g.    1681 = 40^2 + 40 + 41 is NOT prime

END

FUNCTION Prime(number) 

  Prime = number == 2
  IF( (number > 2) * MOD(number,2) ) THEN
    DO i = 3, number^0.5, 2
      IF(MOD(number,i) == 0) THEN
        Prime = 0
        RETURN
      ENDIF
    ENDDO
    Prime = 1
  ENDIF

END</lang>

Icon and Unicon

Procedure shown without a main program. <lang Icon>procedure isprime(n) #: return n if prime (using trial division) or fail if not n = integer(n) | n < 2 then fail # ensure n is an integer greater than 1 every if 0 = (n % (2 to sqrt(n))) then fail return n end </lang>

J

Generally, this task should be accomplished in J using 1&p:. Here we take an approach that's more comparable with the other examples on this page.

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

Java

<lang java>public static boolean prime(long a){ 

  if(a == 2){
     return true;
  }else if(a <= 1 || a % 2 == 0){
     return false;
  }
  long max = (long)Math.sqrt(a);
  for(long n= 3; n <= max; n+= 2){
     if(a % n == 0){ return false; }
  }
  return true;

}</lang>

By Regular Expression

<lang java>public static boolean prime(int n) { 

   return !new String(new char[n]).matches(".?|(..+?)\\1+");

}</lang>

JavaScript

<lang javascript> function isPrime(n) { 

 if (n == 2) {
   return true;
 } else if ((n < 2) || (n % 2 == 0)) {
   return false;
 } else {
   for (var i = 3; i < Math.ceil(Math.sqrt(n)); i += 2) {
     if (n % i == 0)
       return false;
   }
   return true;
 }

}</lang>

Joy

From http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-imper.html <lang joy> DEFINE prime == 

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

</lang>

Liberty BASIC

<lang lb> for n =1 to 50 

 if prime( n) = 1 then print n; " is prime."

next n

wait

function prime( n) 

 if n =2 then
   prime =1
 else
   if ( n <=1) or ( n mod 2 =0) then
       prime =0
   else
       prime =1
       for i = 3 to int( sqr( n)) step 2
           if ( n MOD i) =0 then prime = 0: exit function
       next i
   end if
 end if

end function

end </lang> 

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

LSE64

<lang 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</lang>

Lua

<lang Lua>function IsPrime( n ) 

   if n <= 1 or ( n ~= 2 and n % 2 == 0 ) then
       return false
   end

   for i = 3, math.sqrt(n), 2 do

if n % i == 0 then 

 	    return false

end 

   end

   return true

end</lang>

M4

<lang 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) </lang>

Output: 

0
1

Mathematica

<lang>IsPrime[n_Integer] := 

Module[{k = 2},
 If[n <= 1, Return False];
 If[n == 2, Return True];
 While[k <= Sqrt[n],
  If[Mod[n, k] == 0, Return[False], k++]
  ];
 Return[True]
]</lang>

MATLAB

<lang MATLAB>function isPrime = primalityByTrialDivision(n) 

   if n == 2
       isPrime = true;
       return
   elseif (mod(n,2) == 0) || (n <= 1)
       isPrime = false;
       return
   end
   
   %First n mod (3 to sqrt(n)) is taken. This will me a vector where the
   %first element is equal to n mod 3 and the last element is equal to n
   %mod sqrt(n). Then the all function is applied to that vector. If all
   %of the elements of this vector are non-zero (meaning n is prime) then
   %all() returns true. Otherwise, n is composite, so it returns false.
   %This return value is then assigned to the variable isPrime.
   isPrime = all(mod(n, (3:round(sqrt(n))) ));

end</lang>

Sample Output: <lang MATLAB>>> arrayfun(@primalityByTrialDivision,(1:14))

ans = 

    0     1     1     0     1     0     1     0     0     0     1     0     1     0</lang>

MAXScript

<lang 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
)

</lang>

MUMPS

<lang MUMPS>ISPRIME(N) 

QUIT:(N=2) 1
NEW I,TP
SET TP=+'$PIECE((N/2),".",2)
IF 'TP FOR I=3:2:(N**.5) SET TP=+'$PIECE((N/I),".",2) Q:TP
KILL I
QUIT 'TP</lang>

Usage (0 is false, nonzero is true): 

USER>W $$ISPRIME^ROSETTA(2)
1
USER>W $$ISPRIME^ROSETTA(4)
0
USER>W $$ISPRIME^ROSETTA(7)
1
USER>W $$ISPRIME^ROSETTA(97)
1
USER>W $$ISPRIME^ROSETTA(99)
0

Objeck

<lang objeck> function : IsPrime(n : Int) ~ Bool { 

 if(n <= 1) {
   return false;
 };
 
 for(i := 2; i * i <= n; i += 1;) {           
   if(n % i = 0) {
     return false;
   };
 };
 
 return true;

} </lang>

OCaml

<lang 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</lang>

Octave

This function works on vectors and matrix.

<lang octave>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 ));</lang>

PARI/GP

<lang parigp>trial(n)={ 

 if(n < 4, return(n > 1)); /* Handle negatives */
 forprime(p=2,sqrt(n),
   if(n%p == 0, return(0))
 );
 1

};</lang>

Pascal

Translation of: BASIC

<lang Pascal>program primes;

function prime(n: integer): boolean; var 

 i: integer; max: real;

begin 

 if n = 2 then
   prime := true
 else if (n <= 1) or (n mod 2 = 0) then
   prime := false
 else begin
   prime := true; i := 3; max := sqrt(n);
   while i <= max do begin
     if n mod i = 0 then begin
       prime := false; exit
     end;
     i := i + 2
   end
 end

end;

{ Test and display primes 0 .. 50 } var 

 n: integer;

begin 

 for n := 0 to 50 do
   if (prime(n)) then
     write(n, ' ');

end.</lang>

Output: 

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Perl

A more idiomatic solution: <lang perl>sub prime { my $n = shift || $_; 

   $n % $_ or return for 2 .. sqrt $n;
   $n > 1

}

print join(', ' => grep prime, 1..100), "\n";</lang>

By Regular Expression

JAPH by Abigail 1999 [1] in conference slides 2000 [2]

<lang perl>sub isprime { 

 ('1' x shift) !~ /^1?$|^(11+?)\1+$/

}

  1. A quick test

print join(', ', grep(isprime($_), 0..39)), "\n";</lang>

Perl 6

Works with: Rakudo Star version 2010.09

Here we use a "none" junction which will autothread through the %% "is divisible by" operator to assert that $n is not divisible by 2 or any of the odd numbers up to its square root. Read it just as you would English: "Integer $n is prime if it is greater than one and is divisible by none of 2, 3, whatever + 2, up to but not including whatever is greater than the square root of $n."

<lang perl6>sub prime (Int $n --> Bool) { 

   $n > 1 and $n %% none 2, 3, *+2 ...^ * > sqrt $n;

}</lang>

(No pun indented.)

Testing: <lang>say "$_ is{ "n't" x !prime($_) } prime." for 1 .. 100;</lang>

PHP

<lang php><?php function prime($a) { 

 if (($a % 2 == 0 && $a != 2) || $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";

?></lang>

By Regular Expression

<lang php><?php function prime($a) { 

 return !preg_match('/^1?$|^(11+?)\1+$/', str_repeat('1', $a));

} ?></lang>

PicoLisp

<lang PicoLisp>(de prime? (N) 

  (or
     (= N 2)
     (and
        (> N 1)
        (bit? 1 N)
        (for (D 3  T  (+ D 2))
           (T (> D (sqrt N)) T)
           (T (=0 (% N D)) NIL) ) ) ) )</lang>

PowerShell

<lang powershell>function isPrime ($n) { 

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

}</lang>

PureBasic

<lang PureBasic>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</lang>

Python

The simplest primality test, using trial division:

Works with: Python version 2.5

<lang python>def prime(a): 

   return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1)))</lang>

Another test. Exclude even numbers first:

<lang python>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))</lang>

Yet another test. Exclude multiples of 2 and 3, see http://www.devx.com/vb2themax/Tip/19051:

Works with: Python version 2.4

<lang python>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</lang>

By Regular Expression

Regular expression by "Abigail".
(An explanation is given in "The Story of the Regexp and the Primes"). <lang python>>>> 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] </lang>

R

<lang 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

}</lang>

<lang R>print(lapply(1:100, isPrime))</lang>

REBOL

<lang REBOL> prime?: func [n] [ 

   case [
       n = 2 [ true  ]
       n <= 1 or (n // 2 = 0) [ false ]
       true [
           for i 3 round square-root n 2 [
               if n // i = 0 [ return false ]
           ]
           true
       ]
   ]

] </lang>

<lang REBOL> repeat i 100 [ print [i prime? i]] </lang>

REXX

<lang rexx> /*REXX program tests for primality using (kinda smartish) trial division*/

parse arg n . /*let user choose how many, maybe*/ if n== then n=10000 /*if not, then assume the default*/ p=0 /*a count of primes (so far). */ 

                                      /*I like Heinz's 57 varieties... */
 do j=-57 to n                        /*start in the cellar and work up*/
 if \isprime(j) then iterate          /*if not prime, keep looking.    */
 p=p+1                                /*bump the jelly bean counter.   */
 if length(j)>2 then iterate          /*only show two-digit primes.    */
 say right(j,20) 'is prime.'          /*Just blab about the wee primes.*/
 end

say say "there're" p "primes up to" n '(inclusive).' exit


/*─────────────────────────────────────ISPRIME subroutine───────────────*/ isprime: procedure; arg x /*get the number in question*/ if wordpos(x,'2 3 5 7')\==0 then return 1 /*is it a teacher's pet? */ if x<2 | x//2==0 | x//3==0 then return 0 /*weed out the riff-raff. */ 

                                           /*Note:   //  is modulus.   */
  do j=5 by 6 until j*j>x                  /*skips multiples of three. */
  if x//j==0 | x//(j+2)==0 then return 0   /*do a pair of divides (mod)*/
  end

return 1 /*I'm exhausted, it's prime!*/ </lang> Output when using the defdault input: 

                   2 is prime.
                   3 is prime.
                   5 is prime.
                   7 is prime.
                  11 is prime.
                  13 is prime.
                  17 is prime.
                  19 is prime.
                  23 is prime.
                  29 is prime.
                  31 is prime.
                  37 is prime.
                  41 is prime.
                  43 is prime.
                  47 is prime.
                  53 is prime.
                  59 is prime.
                  61 is prime.
                  67 is prime.
                  71 is prime.
                  73 is prime.
                  79 is prime.
                  83 is prime.
                  89 is prime.
                  97 is prime.

there're 1229 primes up to 10000 (inclusive).

Ruby

<lang 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</lang> The mathn package in the stdlib for Ruby 1.9.2 contains this compact Prime#prime? method: <lang ruby> 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</lang>

Without any fancy stuff: <lang ruby>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</lang>

By Regular Expression

<lang ruby>def isprime(n) 

 '1'*n !~ /^1?$|^(11+?)\1+$/

end</lang>

Scala

<lang scala>def isPrime(n: Int) = n > 1 && (Iterator.from(2) takeWhile (d => d * d <= n) forall (n % _ != 0))</lang>

Scheme

Works with: Scheme version RRS

<lang scheme>(define (prime? number) 

 (define (*prime? divisor)
   (or (> (* divisor divisor) number)
       (and (> (modulo number divisor) 0)
            (*prime? (+ divisor 1)))))
 (and (> number 1)
      (*prime? 2)))</lang>

Seed7

<lang seed7>const func boolean: is_prime (in integer: number) is func 

 result
   var boolean: prime is FALSE;
 local
   var integer: upTo is 0;
   var integer: testNum is 3;
 begin
   if number = 2 then
     prime := TRUE;
   elsif number rem 2 = 0 or number <= 1 then
     prime := FALSE;
   else
     upTo := sqrt(number);
     while number rem testNum <> 0 and testNum <= upTo do
       testNum +:= 2;
     end while;
     prime := testNum > upTo;
   end if;
 end func;</lang>

Original source: [3]

SNOBOL4

<lang SNOBOL4>define('isprime(n)i,max') :(isprime_end) isprime isprime = n 

       le(n,1) :s(freturn)
       eq(n,2) :s(return)
       eq(remdr(n,2),0) :s(freturn)
       max = sqrt(n); i = 1

isp1 i = le(i + 2,max) i + 2 :f(return) 

       eq(remdr(n,i),0) :s(freturn)f(isp1)

isprime_end</lang>

By Patterns

Using the Abigail regex transated to Snobol patterns.

<lang SNOBOL4> define('rprime(n)str,pat1,pat2,m1') :(end_rprime) rprime str = dupl('1',n); rprime = n 

       pat1 = ('1' | )
       pat2 = ('11' arbno('1')) $ m1 (*m1 arbno(*m1))
       str pos(0) (pat1 | pat2) rpos(0) :s(freturn)f(return)

end_rprime

  • # Test and display primes 0 .. 50

loop rprimes = rprimes rprime(n) ' ' 

       n = lt(n,50) n + 1 :s(loop)
       output = rprimes

end</lang>

Output: 

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Standard ML

<lang sml>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</lang>

Tcl

<lang 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

}</lang>

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

Ursala

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

  1. import std
  2. import nat

prime = ~<{0,1}&& -={2,3}!| ~&h&& (all remainder)^Dtt/~& iota@K31 </lang> test program to try it on a few numbers: <lang Ursala>

  1. cast %bL

test = prime* <5,6,7> </lang> output: 

<true,false,true>

V

like joy 

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

Using it 

|11 prime?
=true
|4 prime?
=false
Retrieved from "https://rosettacode.org/wiki/Primality_by_trial_division?oldid=45797"