Primality by trial division

From Rosetta Code

(Redirected from Primality by Trial Division)
Jump to: navigation, search
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.

Contents

[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

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;

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

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

Or more legibly, and with n <= 1 handling 

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

[edit] BASIC

Works with: QuickBasic version 4.5

Returns 1 for prime, 0 for non-prime 

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

Output: 

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

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

static bool isPrime(int n)
        {
            if (n <= 1) return false;
            for (int i = 2; i <= Math.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] 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).
 

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

[edit] Icon and Unicon

Procedure shown without a main program.

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

[edit] Unicon

The Icon solution works in Unicon.

[edit] 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.
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] Mathematica

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

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

Sample Output: 

>> arrayfun(@primalityByTrialDivision,(1:14))
 
ans =
 
     0     1     1     0     1     0     1     0     0     0     1     0     1     0

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

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

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

Translation of: BASIC 

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.

Output: 

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

[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 Star version 2010.08 

sub prime (Int $n --> Bool) {
    $n > 1 and $n %% none 2, 3, *+2 ... sqrt $n;
}

Testing: 

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

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

[edit] By Regular Expression

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

[edit] 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) ) ) ) )

[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

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

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

[edit] Scheme

Works with: Scheme version R5RS 

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

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

[edit] By Patterns

Using the Abigail regex transated to Snobol patterns. 

        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

Output: 

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

[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
Retrieved from "http://rosettacode.org/wiki/Primality_by_trial_division"
Personal tools
Support