Primality by trial division

(Redirected from 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.

Use trial division.

Even numbers over two may be eliminated right away.

A loop from   3   to    n    will suffice,   but other loops are allowed.

360 Assembly

`*        Primality by trial division  26/03/2017PRIMEDIV CSECT         USING  PRIMEDIV,R13       base register         B      72(R15)            skip savearea         DC     17F'0'             savearea         STM    R14,R12,12(R13)    save previous context         ST     R13,4(R15)         link backward         ST     R15,8(R13)         link forward         LR     R13,R15            set addressability         LA     R10,PG             pgi=0         LA     R6,1               i=1       DO WHILE=(C,R6,LE,=F'50')   do i=1 to 50         LR     R1,R6                i         BAL    R14,ISPRIME          call isprime(i)       IF C,R0,EQ,=F'1' THEN         if isprime(i) then         XDECO  R6,XDEC                edit i         MVC    0(4,R10),XDEC+8        output i         LA     R10,4(R10)             pgi+=4       ENDIF    ,                    endif         LA     R6,1(R6)             i++       ENDDO    ,                  enddo i         XPRNT  PG,L'PG            print buffer         L      R13,4(0,R13)       restore previous savearea pointer         LM     R14,R12,12(R13)    restore previous context         XR     R15,R15            rc=0         BR     R14                exit*------- ----   ----------------------------------------ISPRIME  EQU    *                  function isprime(n)       IF C,R1,LE,=F'1' THEN       if n<=1 then         LA     R0,0                 return(0)         BR     R14                  return       ENDIF    ,                  endif       IF C,R1,EQ,=F'2' THEN       if n=2 then         LA     R0,1                 return(1)         BR     R14                  return       ENDIF    ,                  endif         LR     R4,R1              n         N      R4,=X'00000001'    n and 1       IF LTR,R4,Z,R4 THEN         if mod(n,2)=0 then         LA     R0,0                 return(0)         BR     R14                  return       ENDIF    ,                  endif         LA     R7,3               j=3         LA     R5,9               r5=j*j       DO WHILE=(CR,R5,LE,R1)      do j=3 by 2 while j*j<=n         LR     R4,R1                n         SRDA   R4,32                ~         DR     R4,R7                /j       IF LTR,R4,Z,R4 THEN           if mod(n,j)=0 then         LA     R0,0                   return(0)         BR     R14                    return       ENDIF    ,                    endif         LA     R7,2(R7)             j+=2         LR     R5,R7                j         MR     R4,R7                r5=j*j       ENDDO    ,                  enddo j         LA     R0,1               return(1)         BR     R14                return*------- ----   ----------------------------------------PG       DC     CL80' '            bufferXDEC     DS     CL12               temp for xdeco         YREGS         END    PRIMEDIV`
Output:
```  2   3   5   7  11  13  17  19  23  29  31  37  41  43  47
```

ABAP

`class ZMLA_ROSETTA definition  public  create public . public section.   types:    enumber         TYPE          N  LENGTH 60 .  types:    listof_enumber  TYPE TABLE OF enumber .   class-methods IS_PRIME    importing      value(N) type ENUMBER    returning      value(OFLAG) type ABAP_BOOL .  class-methods IS_PRIME_I    importing      value(N) type I    returning      value(OFLAG) type ABAP_BOOL .  protected section.  private section.ENDCLASS.   CLASS ZMLA_ROSETTA IMPLEMENTATION.  * <SIGNATURE>---------------------------------------------------------------------------------------+* | Static Public Method ZMLA_ROSETTA=>IS_PRIME* +-------------------------------------------------------------------------------------------------+* | [--->] N                              TYPE        ENUMBER* | [<-()] OFLAG                          TYPE        ABAP_BOOL* +--------------------------------------------------------------------------------------</SIGNATURE>  method IS_PRIME.    IF n < 2.      oflag = abap_false.      RETURN.    ENDIF.    IF n = 2 or n = 3.      oflag = abap_true.      RETURN.    ENDIF.    IF n mod 2 = 0 or n mod 3 = 0.      oflag = abap_false.      RETURN.    ENDIF.    DATA: lim type enumber,          d   type enumber,          i   TYPE i        VALUE 2.    lim = sqrt( n ).    d   = 5.    WHILE d <= lim.      IF n mod d = 0.        oflag = abap_false.        RETURN.      ENDIF.      d = d + i.      i = 6 - i.  " this modifies 2 into 4 and viceversa    ENDWHILE.    oflag = abap_true.    RETURN.  endmethod.  * <SIGNATURE>---------------------------------------------------------------------------------------+* | Static Public Method ZMLA_ROSETTA=>IS_PRIME_I* +-------------------------------------------------------------------------------------------------+* | [--->] N                              TYPE        I* | [<-()] OFLAG                          TYPE        ABAP_BOOL* +--------------------------------------------------------------------------------------</SIGNATURE>  method IS_PRIME_I.    IF n < 2.      oflag = abap_false.      RETURN.    ENDIF.    IF n = 2 or n = 3.      oflag = abap_true.      RETURN.    ENDIF.    IF n mod 2 = 0 or n mod 3 = 0.      oflag = abap_false.      RETURN.    ENDIF.    DATA: lim type i,          d   type i,          i   TYPE i        VALUE 2.    lim = sqrt( n ).    d   = 5.    WHILE d <= lim.      IF n mod d = 0.        oflag = abap_false.        RETURN.      ENDIF.      d = d + i.      i = 6 - i.  " this modifies 2 into 4 and viceversa    ENDWHILE.    oflag = abap_true.    RETURN.  endmethod.ENDCLASS.`

ACL2

`(defun is-prime-r (x i)   (declare (xargs :measure (nfix (- x i))))   (if (zp (- (- x i) 1))       t       (and (/= (mod x i) 0)            (is-prime-r x (1+ i))))) (defun is-prime (x)   (or (= x 2)       (is-prime-r x 2)))`

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;}`

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

As an alternative, one can use the generic function Prime_Numbers.Is_Prime, as specified in Prime decomposition#Ada, which also implements trial division.

`with Prime_Numbers;  procedure Test_Prime is    package Integer_Numbers is new      Prime_Numbers (Natural, 0, 1, 2);    use Integer_Numbers; begin   if Is_Prime(12) or (not Is_Prime(13)) then       raise Program_Error with "Test_Prime failed!";   end if;end Test_Prime;`

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

ALGOL W

`% returns true if n is prime, false otherwise %% uses trial division                         %logical procedure isPrime ( integer value n ) ;    if n < 3 or not odd( n ) then n = 2    else begin        % odd number > 2 %        integer f, rootN;        logical havePrime;        f         := 3;        rootN     := entier( sqrt( n ) );        havePrime := true;        while f <= rootN and havePrime do begin            havePrime := ( n rem f ) not = 0;            f         := f + 2        end;        havePrime    end isPrime ;`

Test program:

`begin    logical procedure isPrime ( integer value n ) ; algol "isPrime" ;    for i := 0 until 32 do if isPrime( i ) then writeon( i_w := 1,s_w := 1, i )end.`
Output:
```2 3 5 7 11 13 17 19 23 29 31
```

ATS

`(* ****** ****** *)//#include"share/atspre_staload.hats"#include"share/HATS/atspre_staload_libats_ML.hats"//#staload M = "libats/libc/SATS/math.sats"//(* ****** ****** *)//funisqrt(n: intGte(0)): intGte(0) =  \$UNSAFE.cast(\$M.sqrt_double(g0i2f(n)))//funis_prime(n : intGte(2)) : bool =(if(n = 2)then trueelse (  if n % 2 = 0    then false    else (1, (isqrt(n)+1)/2).forall()(lam i => n % (2*i+1) != 0)) (* else *)) (* end of [is_prime] *)//(* ****** ****** *)`

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

AutoIt

`#cs ----------------------------------------------------------------------------  AutoIt Version: 3.3.8.1 Author:         Alexander Alvonellos   Script Function:	Perform primality test on a given integer \$number.	RETURNS: TRUE/FALSE #ce ----------------------------------------------------------------------------Func main()	ConsoleWrite("The primes up to 100 are: " & @LF)	For \$i = 1 To 100 Step 1		If(isPrime(\$i)) Then			If(\$i <> 97) Then				ConsoleWrite(\$i & ", ")			Else				ConsoleWrite(\$i)			EndIf		EndIf	NextEndFunc Func isPrime(\$n)	If(\$n < 2) Then Return False	If(\$n = 2) Then Return True	If(BitAnd(\$n, 1) = 0) Then Return False	For \$i = 3 To Sqrt(\$n) Step 2		If(Mod(\$n, \$i) = 0) Then Return False	Next	Return TrueEndFuncmain()`

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

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 IFEND FUNCTION ' Test and display primes 1 .. 50DECLARE 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
```

IS-BASIC

`100 PROGRAM "Prime.bas"110 FOR X=0 TO 100120   IF PRIME(X) THEN PRINT X;130 NEXT140 DEF PRIME(N)150   IF N=2 THEN160     LET PRIME=-1170   ELSE IF N<=1 OR MOD(N,2)=0 THEN180     LET PRIME=0190   ELSE200     LET PRIME=-1210     FOR I=3 TO CEIL(SQR(N)) STEP 2220       IF MOD(N,I)=0 THEN LET PRIME=0:EXIT FOR230     NEXT240   END IF250 END DEF`

ZX Spectrum Basic

`10 LET n=0: LET p=020 INPUT "Enter number: ";n30 IF n>1 THEN GO SUB 100040 IF p=0 THEN PRINT n;" is not prime!"50 IF p<>0 THEN PRINT n;" is prime!"60 GO TO 101000 REM ***************1001 REM * PRIME CHECK *1002 REM ***************1010 LET p=01020 IF n/2=INT (n/2) THEN RETURN 1030 LET p=11040 FOR i=3 TO SQR (n) STEP 21050 IF n/i=INT (n/i) THEN LET p=0: LET i= SQR (n) 1060 NEXT i1070 RETURN  `
Output:
```15 is not prime!
17 is prime!
119 is not prime!
137 is prime!```

BBC BASIC

`      FOR i% = -1 TO 100        IF FNisprime(i%) PRINT ; i% " is prime"      NEXT      END       DEF FNisprime(n%)      IF n% <= 1 THEN = FALSE      IF n% <= 3 THEN = TRUE      IF (n% AND 1) = 0 THEN = FALSE      LOCAL t%      FOR t% = 3 TO SQR(n%) STEP 2        IF n% MOD t% = 0 THEN = FALSE      NEXT      = TRUE`
Output:
```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```

bc

`/* Return 1 if n is prime, 0 otherwise */define p(n) {    auto i     if (n < 2) return(0)    if (n == 2) return(1)    if (n % 2 == 0) return(0)    for (i = 3; i * i <= n; i += 2) {        if (n % i == 0) return(0)    }    return(1)}`

Befunge

Reads the value to test from stdin and outputs Yes if prime and No if not.

To avoid dealing with Befunge's limited data cells, the implementation is entirely stack-based. However, this requires compressing multiple values into a single stack cell, which imposes an upper limit of 1,046,529 (10232), thus a maximum testable prime of 1,046,527.

`&>:48*:**       \1`!#^_2vv_v#`\*:%*:*84\/*:*84::+<v >::48*:*/\48*:*%%!#v_1^>0"seY" >:#,[email protected]#: "No">#0<`
Output:
(multiple runs)
```0
No
17
Yes
49
No
97
Yes
1042441
No
1046527
Yes```

Bracmat

`  ( prime  =   incs n I inc    .   4 2 4 2 4 6 2 6:?incs      & 2:?n      & 1 2 2 !incs:?I      &   whl        ' ( !n*!n:~>!arg          & div\$(!arg.!n)*!n:~!arg          & (!I:%?inc ?I|!incs:%?inc ?I)          & !n+!inc:?n          )      & !n*!n:>!arg  )& 100000000000:?p&   whl  ' ( !p+1:<100000000100:?p    & (   prime\$!p        & out\$!p      |       )    )& ;`
Output:
```100000000003
100000000019
100000000057
100000000063
100000000069
100000000073
100000000091```

Burlesque

`fcL[2==`

Implicit trial division is done by the fc function. It checks if the number has exactly two divisors.

Version not using the fc function:

`blsq ) 11^^2\/[email protected]%{0==}ayn!1blsq ) 12^^2\/[email protected]%{0==}ayn!0blsq ) 13^^2\/[email protected]%{0==}ayn!1`

Explanation. Given n generates a block containing 2..n-1. Calculates a block of modolus and check if it contains 0. If it contains 0 it is not a prime.

C

`int is_prime(unsigned int n){	unsigned int p;	if (!(n & 1) || n < 2 ) return n == 2; 	/* comparing p*p <= n can overflow */	for (p = 3; p <= n/p; p += 2)		if (!(n % p)) return 0;	return 1;}`

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;}`

C#

`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;        }`

Chapel

Translation of: C++
`proc is_prime(n){    if n == 2 then        return true;    if n <= 1 || n % 2 == 0 then        return false;    for i in 3..floor(sqrt(n)):int by 2 do        if n % i == 0 then            return false;    return true;}`

Clojure

The function used in both versions:

`(defn divides? [k n] (zero? (mod k n)))`

Testing divisors are in range from 3 to  n    with step 2:

`(defn prime? [x]  (or (= 2 x)      (= 3 x)      (and (< 1 x)           (odd? x)           (not-any? (partial divides? x)                     (range 3 (inc (Math/sqrt x)) 2)))))`

Testing only prime divisors:

`(declare prime?) (def primes (filter prime? (range))) (defn prime? [x]  (or (= 2 x)      (and (integer? x)           (< 1 x)           (not-any? (partial divides? x)                     (take-while (partial >= (Math/sqrt x)) primes)))))`

CMake

`# Prime predicate: does n be a prime number? Sets var to true or false.function(primep var n)  if(n GREATER 2)    math(EXPR odd "\${n} % 2")    if(odd)      # n > 2 and n is odd.      set(factor 3)      # Loop for odd factors from 3, while factor <= n / factor.      math(EXPR quot "\${n} / \${factor}")      while(NOT factor GREATER quot)        math(EXPR rp "\${n} % \${factor}")        # Trial division        if(NOT rp)          # factor divides n, so n is not prime.          set(\${var} false PARENT_SCOPE)          return()        endif()        math(EXPR factor "\${factor} + 2")       # Next odd factor        math(EXPR quot "\${n} / \${factor}")      endwhile(NOT factor GREATER quot)      # Loop found no factor, so n is prime.      set(\${var} true PARENT_SCOPE)    else()      # n > 2 and n is even, so n is not prime.      set(\${var} false PARENT_SCOPE)    endif(odd)  elseif(n EQUAL 2)    set(\${var} true PARENT_SCOPE)       # 2 is prime.  else()    set(\${var} false PARENT_SCOPE)      # n < 2 is not prime.  endif()endfunction(primep)`
`# Quick example.foreach(i -5 1 2 3 37 39)  primep(b \${i})  if(b)    message(STATUS "\${i} is prime.")  else()    message(STATUS "\${i} is _not_ prime.")  endif(b)endforeach(i)`

COBOL

`       Identification Division.       Program-Id. Primality-By-Subdiv.        Data Division.       Working-Storage Section.       78  True-Val  Value 0.       78  False-Val Value 1.        Local-Storage Section.       01  lim Pic 9(10).       01  i   Pic 9(10).        Linkage Section.       01  num    Pic 9(10).       01  result Pic 9.        Procedure Division Using num result.       Main.           If num <= 1               Move False-Val To result               Goback           Else If num = 2               Move True-Val To result               Goback           End-If            Compute lim = Function Sqrt(num) + 1           Perform Varying i From 3 By 1 Until lim < i               If Function Mod(num, i) = 0                   Move False-Val To result                   Goback               End-If           End-Perform            Move True-Val To Result            Goback           .`

CoffeeScript

`is_prime = (n) ->  # simple prime detection using trial division, works  # for all integers  return false if n <= 1 # by definition  p = 2  while p * p <= n    return false if n % p == 0    p += 1  true for i in [-1..100]  console.log i if is_prime i`

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

Alternate solution

I use Allegro CL 10.1

`;; Project : Primality by trial division (defun prime(n)         (setq flag 0)         (loop for i from 2 to (- n 1) do                 (if (= (mod n i) 0)                     (setq flag 1)))                 (if (= flag 0)                     (format t "~d is a prime number" n)                     (format t "~d is not a prime number" n)))(prime 7)(prime 8)`

Output:

```7 is a prime number
8 is not a prime number
```

D

Simple Version

`import std.stdio, std.algorithm, std.range, std.math; bool isPrime1(in int n) pure nothrow {    if (n == 2)        return true;    if (n <= 1 || (n & 1) == 0)        return false;     for(int i = 3; i <= real(n).sqrt; i += 2)        if (n % i == 0)            return false;    return true;} void main() {    iota(2, 40).filter!isPrime1.writeln;}`
Output:
```[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
```

Version with excluded multiplies of 2 and 3

Same output.

`bool isPrime2(It)(in It n) pure nothrow {    // Adapted from: http://www.devx.com/vb2themax/Tip/19051    // Test 1, 2, 3 and multiples of 2 and 3:    if (n == 2 || n == 3)        return true;    else if (n < 2 || n % 2 == 0 || n % 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 n.    for (It div = 5, inc = 2; div ^^ 2 <= n; div += inc, inc = 6 - inc)        if (n % div == 0)            return false;     return true;} void main() {    import std.stdio, std.algorithm, std.range;     iota(2, 40).filter!isPrime2.writeln;}`

Two Way Test

Odd divisors is generated both from increasing and decreasing sequence, may improve performance for numbers that have large minimum factor. Same output.

`import std.stdio, std.algorithm, std.range, std.math; bool isPrime3(T)(in T n) pure nothrow {    if (n % 2 == 0 || n <= 1)        return n == 2;    T head = 3, tail = (cast(T)real(n).sqrt / 2) * 2 + 1;    for ( ; head <= tail ; head +=2, tail -= 2)        if ((n % head) == 0 || (n % tail) == 0)            return false;    return true;} void main() {    iota(2, 40).filter!isPrime3.writeln;}`

Delphi

First

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

Second

`function IsPrime(const x: integer): Boolean;var  i: integer;begin  i := 2;  repeat    if X mod i = 0 then    begin      Result := False;      Exit;    end;    Inc(i);  until i > Sqrt(x);  Result := True;end;`

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

EchoLisp

`(lib 'sequences) ;; Try divisors iff n = 2k + 1(define (is-prime? p)	(cond	[(< p 2) #f]	[(zero? (modulo p 2)) (= p 2)]	[else 	(for/and ((d [3 5 .. (1+ (sqrt p))] ))  (!zero? (modulo p d)))])) (filter is-prime? (range 1 100))    → (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) ;; Improve performance , try divisors iff  n = 6k+1 or n = 6k+5(define (is-prime? p)	(cond	[(< p 2) #f]	[(zero? (modulo p 2)) (= p 2)]	[(zero? (modulo p 3)) (= p 3)]	[(zero? (modulo p 5)) (= p 5)]	[else  ;; step 6 : try divisors 6n+1 or 6n+5		(for ((d [7 13 .. (1+ (sqrt p))] ))  			#:break (zero? (modulo p d)) => #f			#:break (zero? (modulo p (+ d 4))) => #f			#t )])) (filter is-prime? (range 1 100))    → (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)`

Eiffel

`class	APPLICATION create	make feature 	make                -- Tests the feature is_prime.		do			io.put_boolean (is_prime (1))			io.new_line			io.put_boolean (is_prime (2))			io.new_line			io.put_boolean (is_prime (3))			io.new_line			io.put_boolean (is_prime (4))			io.new_line			io.put_boolean (is_prime (97))			io.new_line			io.put_boolean (is_prime (15589))			io.new_line		end 	is_prime (n: INTEGER): BOOLEAN                -- Is 'n' a prime number?		require			positiv_input: n > 0		local			i: INTEGER			max: REAL_64			math: DOUBLE_MATH		do			create math			if n = 2 then				Result := True			elseif n <= 1 or n \\ 2 = 0 then				Result := False			else				Result := True				max := math.sqrt (n)				from					i := 3				until					i > max				loop					if n \\ i = 0 then						Result := False					end					i := i + 2				end			end		end end`
```False
True
True
False
True
False```

Elixir

Translation of: Erlang
`defmodule RC do  def is_prime(2), do: true  def is_prime(n) when n<2 or rem(n,2)==0, do: false  def is_prime(n), do: is_prime(n,3)   def is_prime(n,k) when n<k*k, do: true  def is_prime(n,k) when rem(n,k)==0, do: false  def is_prime(n,k), do: is_prime(n,k+2)end IO.inspect for n <- 1..50, RC.is_prime(n), do: n`
Output:
```[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
```

Emacs Lisp

Use cl.el library.

`(defun prime (a)  (not (or (< a 2)           (loop for x from 2 to (sqrt a)                 when (zerop (% a x))                 return t))))`

More concise, a little bit faster:

`(defun prime2 (a)  (and (> a 1)       (loop for x from 2 to (sqrt a)             never (zerop (% a x)))))`

A little bit faster:

`(defun prime3 (a)  (and (> a 1)       (or (= a 2) (oddp a))       (loop for x from 3 to (sqrt a) by 2             never (zerop (% a x)))))`

More than 2 times faster, than the previous, doesn't use loop macro:

`(defun prime4 (a)  (not (or (< a 2)           (some (lambda (x) (zerop (% a x))) (number-sequence 2 (sqrt a))))))`

Almost 2 times faster, than the previous:

`(defun prime5 (a)  (not (or (< a 2)           (and (/= a 2) (evenp a))           (some (lambda (x) (zerop (% a x))) (number-sequence 3 (sqrt a) 2)))))`

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

ERRE

`PROGRAM PRIME_TRIAL PROCEDURE ISPRIME(N%->OK%)      LOCAL T%      IF N%<=1 THEN OK%=FALSE  EXIT PROCEDURE END IF      IF N%<=3 THEN OK%=TRUE EXIT PROCEDURE END IF      IF (N% AND 1)=0 THEN OK%=FALSE EXIT PROCEDURE END IF      FOR T%=3 TO SQR(N%) STEP 2 DO        IF N% MOD T%=0 THEN OK%=FALSE EXIT PROCEDURE END IF      END FOR      OK%=TRUEEND PROCEDURE BEGIN       FOR I%=1 TO 100 DO         ISPRIME(I%->OK%)         IF OK% THEN PRINT(i%;"is prime") END IF      END FOR END PROGRAM`
Output:
```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
```

Euphoria

`function is_prime(integer n)    if n<=2 or remainder(n,2)=0 then        return 0    else        for i=3 to sqrt(n) by 2 do            if remainder(n,i)=0 then                return 0            end if        end for        return 1    end ifend function`

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

FALSE

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

FBSL

The second function (included by not used) I would have thought would be faster because it lacks the SQR() function. As it happens, the first is over twice as fast.

`#APPTYPE CONSOLE FUNCTION ISPRIME(n AS INTEGER) AS INTEGER    IF n = 2 THEN        RETURN TRUE    ELSEIF n <= 1 ORELSE n MOD 2 = 0 THEN        RETURN FALSE    ELSE        FOR DIM i = 3 TO SQR(n) STEP 2            IF n MOD i = 0 THEN                RETURN FALSE            END IF        NEXT        RETURN TRUE    END IFEND FUNCTION FUNCTION ISPRIME2(N AS INTEGER) AS INTEGER    IF N <= 1 THEN RETURN FALSE    DIM I AS INTEGER = 2    WHILE I * I <= N        IF N MOD I = 0 THEN            RETURN FALSE        END IF        I = I + 1    WEND    RETURN TRUEEND FUNCTION ' Test and display primes 1 .. 50DIM n AS INTEGER FOR n = 1 TO 50    IF ISPRIME(n) THEN        PRINT n, " ";    END IFNEXT PAUSE`
Output:
```2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Press any key to continue...
```

Forth

`: prime? ( n -- f )        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
` 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`

FreeBASIC

`' FB 1.05.0 Win64 Function isPrime(n As Integer) As Boolean  If n < 2 Then Return False  If n = 2 Then Return True  If n Mod 2  = 0 Then Return False  Dim limit As Integer = Sqr(n)  For i As Integer = 3 To limit Step 2    If n Mod i = 0 Then Return False  Next  Return TrueEnd Function ' To test this works, print all primes under 100For i As Integer = 1 To 99  If isPrime(i) Then     Print Str(i); " ";   End IfNext Print : PrintPrint "Press any key to quit"Sleep`
Output:
```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
```

F#

`open NUnit.Frameworkopen FsUnitlet inline isPrime n = not ({uint64 2..uint64 (sqrt (double n))} |> Seq.exists (fun (i:uint64) -> uint64 n % i = uint64 0))[<Test>]let ``Validate that 2 is prime`` () =  isPrime 2 |> should equal true [<Test>]let ``Validate that 4 is not prime`` () =  isPrime 4 |> should equal false [<Test>]let ``Validate that 3 is prime`` () =  isPrime 3 |> should equal true [<Test>]let ``Validate that 9 is not prime`` () =  isPrime 9 |> should equal false [<Test>]let ``Validate that 5 is prime`` () =  isPrime 5 |> should equal true [<Test>]let ``Validate that 277 is prime`` () =  isPrime 277 |> should equal true`
Output:
```> isPrime 1111111111111111111UL;;
val it : bool = true
```

and if you want to test really big numbers, use System.Numerics.BigInteger, but it's slower:

` let isPrimeI x =    if x < 2I then false else    if x = 2I then true else    if x % 2I = 0I then false else    let rec test n =      if n * n > x then true else      if x % n = 0I then false else test (n + 2I) in test 3I`

If you have a lot of prime numbers to test, caching a sequence of primes can speed things up considerably, so you only have to do the divisions against prime numbers.

`let rec primes = Seq.cache(Seq.append (seq[ 2; 3; 5 ]) (Seq.unfold (fun state -> Some(state, state + 2)) 7 |> Seq.filter (fun x -> IsPrime x))) and IsPrime number =    let rec IsPrimeCore number current limit =        let cprime = primes |> Seq.nth current        if cprime >= limit then            true        else if number % cprime = 0 then            false        else            IsPrimeCore number (current + 1) (number/cprime)     if number = 2 then        true    else if number < 2 then        false    else        IsPrimeCore number 0 number`

FunL

`import math.sqrt def  isPrime( 2 )      =  true  isPrime( n )    | n < 3 or 2|n  =  false    | otherwise     =  (3..int(sqrt(n)) by 2).forall( (/|n) ) (10^10..10^10+50).filter( isPrime ).foreach( println )`
Output:
```10000000019
10000000033
```

FutureBasic

`include "ConsoleWindow" def tab 6 local fn isPrime( n as long ) as Booleandim as long idim as Boolean result if n < 2 then result = _false : exit fnif n = 2 then result = _true  : exit fnif n mod 2 == 0  then result = _false : exit fnresult = _truefor i = 3 to int( n^.5 ) step 2  if n mod i == 0 then result = _false : exit fnnext iend fn = result dim as long i, j print "Prime numbers between 0 and 1000:"for i = 0 to 1000  if ( fn isPrime(i) != _false )    print i, : j++    if j mod 10 == 0 then print  end ifnext`

Output:

```Prime numbers between 0 and 1000:
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    101   103   107   109   113
127   131   137   139   149   151   157   163   167   173
179   181   191   193   197   199   211   223   227   229
233   239   241   251   257   263   269   271   277   281
283   293   307   311   313   317   331   337   347   349
353   359   367   373   379   383   389   397   401   409
419   421   431   433   439   443   449   457   461   463
467   479   487   491   499   503   509   521   523   541
547   557   563   569   571   577   587   593   599   601
607   613   617   619   631   641   643   647   653   659
661   673   677   683   691   701   709   719   727   733
739   743   751   757   761   769   773   787   797   809
811   821   823   827   829   839   853   857   859   863
877   881   883   887   907   911   919   929   937   941
947   953   967   971   977   983   991   997
```

Gambas

`'Reworked from the BBC Basic example Public Sub Main()Dim iNum As Integer For iNum = 1 To 100  If FNisprime(iNum) Then Print iNum & " is prime"Next End'___________________________________________________Public Sub FNisprime(iNum As Integer) As BooleanDim iLoop As IntegerDim bReturn As Boolean = True If iNum <= 1 Then bReturn = FalseIf iNum <= 3 Then bReturn = TrueIf (iNum And 1) = 0 Then bReturn = False For iLoop = 3 To Sqr(iNum) Step 2  If iNum Mod iLoop = 0 Then bReturn = FalseNext Return bReturn End`

Output:

```1 is prime
3 is prime
5 is prime
7 is prime
11 is prime
......
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime```

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);                              # [ 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 ]`

Go

`func IsPrime(n int) bool {	if n < 0 { n = -n }	switch {        case n == 2:		return true	case n < 2 || n % 2 == 0:		return false 	default:		for i = 3; i*i <= n; i += 2 {			if n % i == 0 { return false }		}	}	return true}`

Or, using recursion:

`func IsPrime(n int) bool {	if n < 0 { n = -n }	if n <= 2 { 		return n == 2 	}	return n % 2 != 0 && isPrime_r(n, 3)} func isPrime_r(n, i int) bool {	if i*i <= n {		return n % i != 0 && isPrime_r(n, i+2)	}	return true}`

Groovy

`def isPrime = {    it == 2 ||     it > 1 &&    (2..Math.max(2, (int) Math.sqrt(it))).every{ k -> it % k != 0 }} (0..20).grep(isPrime)`
Output:
```[2, 3, 5, 7, 11, 13, 17, 19]
```

(used here and here). The basic divisibility test by odd numbers:

`isPrime n = n==2 || n>2 && all ((> 0).rem n) (2:[3,5..floor.sqrt.fromIntegral \$ n+1])`

Testing by prime numbers only is faster. Primes list is saved for reuse. Precalculation of primes pays off if testing more than just a few numbers, and/or primes are generated efficiently enough:

`noDivsBy factors n = foldr (\f r-> f*f>n || ((rem n f /= 0) && r)) True factors  -- primeNums = filter (noDivsBy [2..]) [2..]--           = 2 : filter (noDivsBy [3,5..]) [3,5..] primeNums = 2 : 3 : filter (noDivsBy \$ tail primeNums) [5,7..] isPrime n = n > 1 && noDivsBy primeNums n`

Any increasing unbounded sequence of numbers that includes all primes (above the first few, perhaps) could be used with the testing function `noDivsBy` to define the `isPrime` function -- but using just primes is better, produced e.g. by Sieve of Eratosthenes, or `noDivsBy` itself can be used to define `primeNums` as shown above, because it stops when the square root is reached (so there's no infinite recursion, no "vicious circle").

A less efficient, more basic variant:

`isPrime n = n > 1 && []==[i | i <- [2..n-1], rem n i == 0]`

The following is an attempt at improving it, resulting in absolutely worst performing prime testing code I've ever seen, ever. A curious oddity.

`isPrime n = n > 1 && []==[i | i <- [2..n-1], isPrime i && rem n i == 0]`

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 primeEND 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   ENDIFEND`

Icon and Unicon

Procedure shown without a main program.

`procedure isprime(n)                            #: return n if prime (using trial division) or failif not n = integer(n) | n < 2 then fail         # ensure n is an integer greater than 1every if 0 = (n % (2 to sqrt(n))) then failreturn nend`

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.'`

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;}`

By Regular Expression

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

JavaScript

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

Joy

From here

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

jq

def is_prime:

```  if . == 2 then true
else 2 < . and . % 2 == 1 and
. as \$in
| ((\$in + 1) | sqrt) as \$m
| ((((\$m - 1) / 2) | floor) + 1) as \$max
| all( range(1; \$max) ; \$in % ((2 * .) + 1) > 0 )
end;
```

Example -- the command line is followed by alternating lines of input and output: \$ jq -f is_prime.jq

```-2
false
1
false
2
true
100
false
```

Note: if your jq does not have all, the following will suffice:

```def all(generator; condition):
reduce generator as \$i (true; . and (\$i|condition));
```

Julia

Julia already has an isprime function, so this function has the verbose name isprime_trialdivision to avoid overriding the built-in function. Note this function relies on the fact that Julia skips for-loops having invalid ranges. Otherwise the function would have to include additional logic to check the odd numbers less than 9.

`function isprime_trialdivision{T<:Integer}(n::T)    1 < n || return false    n != 2 || return true    isodd(n) || return false    for i in 3:isqrt(n)        n%i != 0 || return false    end    return trueend n = 100a = filter(isprime_trialdivision, [1:n]) if all(a .== primes(n))    println("The primes <= ", n, " are:\n    ", a)else    println("The function does not accurately calculate primes.")end`
Output:
```The primes <= 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]
```

K

`   isprime:{(x>1)&&/x!'2_!1+_sqrt x}   &isprime'!1002 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97`

Kotlin

`// version 1.1.2fun isPrime(n: Int): Boolean {    if (n < 2) return false    if (n % 2 == 0) return n == 2    val limit = Math.sqrt(n.toDouble()).toInt()    return (3..limit step 2).none { n % it == 0 }} fun main(args: Array<String>) {    // test by printing all primes below 100 say    (2..99).filter { isPrime(it) }.forEach { print("\$it ") }}`
Output:
```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
```

Liberty BASIC

`print "Rosetta Code - Primality by trial division"print[start]input "Enter an integer: "; xif x=0 then print "Program complete.": endif isPrime(x) then print x; " is prime" else print x; " is not prime"goto [start] function isPrime(p)    p=int(abs(p))    if p=2 or then isPrime=1: exit function 'prime    if p=0 or p=1 or (p mod 2)=0 then exit function 'not prime    for i=3 to sqr(p) step 2        if (p mod i)=0 then exit function 'not prime    next i    isPrime=1end function`
Output:
```Rosetta Code - Primality by trial division

Enter an integer: 1
1 is not prime
Enter an integer: 2
2 is prime
Enter an integer:
Program complete.```

Lingo

`on isPrime (n)    if n<=1 or (n>2 and n mod 2=0) then return FALSE    sq = sqrt(n)    repeat with i = 3 to sq        if n mod i = 0 then return FALSE    end repeat    return TRUEend`
`primes = []repeat with i = 0 to 100    if isPrime(i) then primes.add(i)end repeatput primes`
Output:
```-- [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]
```

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 "trueend`

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`

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 trueend`

Type of number Decimal.

M2000 Interpreter

`       Inventory [email protected], [email protected]      IsPrime=lambda  Known1 (x as decimal) -> {            =0=1            if exist(Known1, x) then =1=1 : exit            if x<=5 OR frac(x) then {if x == 2 OR x == 3 OR x == 5 then Append Known1, x  : =1=1            Break}            if frac(x/2) else exit            if frac(x/3) else exit            x1=sqrt(x):d = [email protected]            {if frac(x/d ) else exit                  d += 2: if d>x1 then Append Known1, x : =1=1 : exit                  if frac(x/d) else exit                  d += 4: if d<= x1 else Append Known1, x :  =1=1: exit             loop}      }       i=2      While Len(Known1)<20 {            dummy=Isprime(i)                        i++      }      Print "first ";len(known1);" primes"      Print Known1      Print "From 110 to 130"      count=0      For i=110 to 130 {            If isPrime(i) Then Print i, : count++      }      Print      Print "Found ";count;" primes" `

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

Maple

This could be coded in myriad ways; here is one.

`TrialDivision := proc( n :: integer )        if n <= 1 then                false        elif n = 2 then                true        elif type( n, 'even' ) then                false        else                for local i from 3 by 2 while i * i <= n do                        if irem( n, i ) = 0 then                                return false                        end if                end do;                true        end ifend proc:`

Using this to pick off the primes up to 30, we get:

`> select( TrialDivision, [seq]( 1 .. 30 ) );                  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]`

Here is a way to check that TrialDivision above agrees with Maple's built-in primality test (isprime).

`> N := 10000: evalb( select( TrialDivision, [seq]( 1 .. N ) ) = select( isprime, [seq]( 1 .. N ) ) );                                  true`

Mathematica

`IsPrime[n_Integer] := Block[{},  If[n <= 1, Return[False]];  If[n == 2, Return[True]]; If[Mod[n, 2] == 0, Return[False]];  For[k = 3, k <= Sqrt[n], k += 2, If[Mod[n, k] == 0, Return[False]]];  Return[True]]`

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 be 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`

Maxima

`isprme(n):= catch(  for k: 2 thru sqrt(n) do if mod(n, k)=0 then throw(false),  true); map(isprme, [2, 3, 4, 65, 100, 181, 901]);/* [true, true, false, false, false, true, false] */`

МК-61/52

`П0	1	-	x#0	34	2	-	/-/	x<0	32ИП0	2	/	{x}	x#0	343	П4	ИП0	ИП4	/	{x}	x#0	34	КИП4	КИП4ИП0	КвКор	ИП4	-	x<0	16	1	С/П	0	С/П`

MUMPS

`ISPRIME(N) QUIT:(N=2) 1 NEW I,R SET R=N#2 IF R FOR I=3:2:(N**.5) SET R=N#I Q:'R KILL I QUIT R`

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)
7
USER>W \$\$ISPRIME^ROSETTA(99)
0```

NetRexx

`/* NetRexx */ options replace format comments java crossref savelog symbols nobinary parse arg nbr rangeBegin rangeEnd . if nbr = '' | nbr = '.' then do  if rangeBegin = '' | rangeBegin = '.' then rangeBegin = 1  if rangeEnd   = '' | rangeEnd   = '.' then rangeEnd   = 100  if rangeEnd > rangeBegin then direction = 1                           else direction = -1   say 'List of prime numbers from' rangeBegin 'to' rangeEnd':'  primes = ''  loop nn = rangeBegin to rangeEnd by direction    if isPrime(nn) then primes = primes nn    end nn    primes = primes.strip    say '  'primes.changestr(' ', ',')    say '  Total number of primes:' primes.words  endelse do  if isPrime(nbr) then say nbr.right(20) 'is prime'                  else say nbr.right(20) 'is not prime'  end return method isPrime(nbr = long) public static binary returns boolean   ip = boolean   select    when nbr < 2 then do      ip = isFalse      end    when '2 3 5 7'.wordpos(Rexx(nbr)) \= 0 then do      -- crude shortcut ripped from the Rexx example      ip = isTrue      end    when  nbr // 2 == 0 | nbr // 3 == 0 then do      -- another shortcut permitted by the one above      ip = isFalse      end    otherwise do      nn = long      nnStartTerm = long 3 -- a reasonable start term - nn <= 2 is never prime      nnEndTerm = long Math.ceil(Math.sqrt(nbr)) -- a reasonable end term      ip = isTrue -- prime the pump (pun intended)      loop nn = nnStartTerm to nnEndTerm by 2         -- Note: in Rexx and NetRexx "//" is the 'remainder of division operator' (which is not the same as modulo)        if nbr // nn = 0 then do          ip = isFalse          leave nn          end        end nn      end    end   return ip method isTrue public static returns boolean  return 1 == 1 method isFalse public static returns boolean  return \isTrue`
Output:
```\$ java -cp . RCPrimality
List of prime numbers from 1 to 100:
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
Total number of primes: 25

\$ java -cp . RCPrimality 91
91 is not prime

\$ java -cp . RCPrimality 101
101 is prime

\$ java -cp . RCPrimality . . 25
List of prime numbers from 1 to 25:
2,3,5,7,11,13,17,19,23
Total number of primes: 9

\$ java -cp . RCPrimality . 9900 10010
List of prime numbers from 9900 to 10010:
9901,9907,9923,9929,9931,9941,9949,9967,9973,10007,10009
Total number of primes: 11

\$ java -cp . RCPrimality . -57 1
List of prime numbers from -57 to 1:

Total number of primes: 0

\$ java -cp . RCPrimality . 100 -57
List of prime numbers from 100 to -57:
97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2
Total number of primes: 25```

Rexx version reimplemented in NetRexx

Translation of: REXX
`/* NetRexx */ options replace format comments java crossref savelog symbols nobinary /*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... */  loop 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 j.length>2 then iterate           /*only show two-digit primes.    */  say j.right(20) 'is prime.'          /*Just blab about the wee primes.*/  end saysay "there're" p "primes up to" n '(inclusive).'exit /*-------------------------------------ISPRIME subroutine---------------*/method isprime(x) public static returns boolean--isprime: procedure; arg x                   /*get the number in question*/if '2 3 5 7'.wordpos(x)\==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.   */   loop 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!*/`

Nim

`import sequtils, math proc prime(a: int): bool =  if a == 2: return true  if a < 2 or a mod 2 == 0: return false  for i in countup(3, sqrt(a.float).int, 2):    if a mod i == 0:      return false  return true template any(sequence, operation: expr): expr =  var result {.gensym.}: bool = false  for i in 0 .. <sequence.len:    let it {.inject.} = sequence[i]    result = operation    if result:      break  result proc prime2(a: int): bool =  result = not (a < 2 or any(toSeq(2 .. sqrt(a.float).int), a mod it == 0)) proc prime3(a: int): bool =  if a == 2: return true  if a < 2 or a mod 2 == 0: return false  return not any(toSeq countup(3, sqrt(a.float).int, 2), a mod it == 0) for i in 2..30:  echo i, " ", prime(i)`

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;}`

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`

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  endforendfunction % as test, print prime numbers from 1 to 100p = [1:100];pv = isthisprime(p);disp(p( pv ));`

Oforth

`Integer method: isPrime| i |   self 1 <= ifTrue: [ false return ]   self 3 <= ifTrue: [ true return ]   self isEven ifTrue: [ false return ]   3 self sqrt asInteger for: i [ self i mod ifzero: [ false return ] ]   true ;`
Output:
```#isPrime 1000 seq filter println
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 8
9, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181
, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281
, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397
, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503
, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619
, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743
, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863
, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
]```

Oz

`   fun {Prime N}      local IPrime in	 fun {IPrime N Acc}	    if N < Acc*Acc then true	    elseif (N mod Acc) == 0 then false	    else {IPrime N Acc+1}	    end	 end	 if N < 2 then false	 else {IPrime N 2} end      end   end`

PARI/GP

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

Panda

In Panda you write a boolean function by making it filter, either returning it's input or nothing.

`fun prime(p) type integer->integer  p.gt(1) where q=p.sqrt NO(p.mod(2..q)==0) 1..100.prime`

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  endend; { 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
```

improved using number wheel

Library: primTrial
Works with: Free Pascal
`program TestTrialDiv;{\$IFDEF FPC}  {\$MODE DELPHI}{\$Smartlink ON}{\$ELSE}  {\$APPLICATION CONSOLE}// for Delphi{\$ENDIF}uses  primtrial;{ Test and display primes 0 .. 50 }begin  repeat    write(actPrime,' ');  until nextPrime > 50;end.`
Output
```2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
```

Perl

A simple idiomatic solution:

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

Excluding multiples of 2 and 3

One of many ways of writing trial division using a mod-6 wheel. Almost 2x faster than the simple method shown earlier.

`sub isprime {  my \$n = shift;  return (\$n >= 2) if \$n < 4;  return unless \$n % 2  &&  \$n % 3;  my \$sqrtn = int(sqrt(\$n));  for (my \$i = 5; \$i <= \$sqrtn; \$i += 6) {    return unless \$n % \$i && \$n % (\$i+2);  }  1;}my \$s = 0;\$s += !!isprime(\$_) for 1..100000;print "Pi(100,000) = \$s\n";`

By Regular Expression

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

While this is extremely clever and often used for Code golf, it should never be used for real work (it is extremely slow and uses lots of memory).

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

Perl 6

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

`sub prime (Int \$i --> Bool) {    \$i > 1 and so \$i %% none 2..\$i.sqrt;}`

This can easily be improved in two ways. First, we generate the primes so we only divide by those, instead of all odd numbers. Second, we memoize the result using the //= idiom of Perl, which does the right-hand calculation and assigns it only if the left side is undefined. We avoid recalculating the square root each time. Note the mutual recursion that depends on the implicit laziness of list evaluation:

`my @primes = 2, 3, 5, -> \$p { (\$p+2, \$p+4 ... &prime)[*-1] } ... *;my @isprime = False,False;   # 0 and 1 are not prime by definitionsub prime(\$i) {    my \limit = \$i.sqrt.floor;    @isprime[\$i] //= so (\$i %% none @primes ...^ { \$_ > limit })} say "\$_ is{ "n't" x !prime(\$_) } prime." for 1 .. 100;`

Phix

`function is_prime(integer n)    if n<2 then return 0 end if    if n=2 then return 1 end if    if remainder(n,2)=0 then return 0 end if    for i=3 to floor(sqrt(n)) by 2 do        if remainder(n,i)=0 then            return 0        end if    end for    return 1end function`

PHP

`<?phpfunction 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"; ?>`

By Regular Expression

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

PicoLisp

`(de prime? (N)   (or      (= N 2)      (and         (> N 1)         (bit? 1 N)         (let S (sqrt N)            (for (D 3  T  (+ D 2))               (T (> D S) T)               (T (=0 (% N D)) NIL) ) ) ) ) )`

PL/I

`is_prime: procedure (n) returns (bit(1));   declare n fixed (15);   declare i fixed (10);    if n < 2 then return ('0'b);   if n = 2 then return ('1'b);   if mod(n, 2) = 0 then return ('0'b);    do i = 3 to sqrt(n) by 2;      if mod(n, i) = 0 then return ('0'b);   end;   return ('1'b);end is_prime;`

PowerShell

` function isPrime (\$n) {    if (\$n -eq 1) {\$false}     elseif (\$n -eq 2) {\$true}    elseif (\$n -eq 3) {\$true}    else{        \$m = [Math]::Floor([Math]::Sqrt(\$n))        (@(2..\$m | where {(\$_ -lt \$n)  -and (\$n % \$_ -eq 0) }).Count -eq 0)    }}1..15 | foreach{"isPrime \$_ : \$(isPrime \$_)"}`

Output:

```isPrime 1 : False
isPrime 2 : True
isPrime 3 : True
isPrime 4 : False
isPrime 5 : True
isPrime 6 : False
isPrime 7 : True
isPrime 8 : False
isPrime 9 : False
isPrime 10 : False
isPrime 11 : True
isPrime 12 : False
isPrime 13 : True
isPrime 14 : False
isPrime 15 : False```

Prolog

The following predicate showcases Prolog's support for writing predicates suitable for both testing and generating. In this case, assuming the Prolog implemenation supports indefinitely large integers, prime(N) can be used to generate primes until memory is exhausted.

`prime(2).prime(N) :-   between(3, inf, N),  1 is N mod 2,             % odd  M is floor(sqrt(N+1)),    % round-off paranoia   Max is (M-1) // 2,        % integer division  forall( between(1, Max, I), N mod (2*I+1) > 0 ).`

Example using SWI-Prolog:

```?- time( (bagof( P, (prime(P), ((P > 100000, !, fail); true)), Bag),
length(Bag,N),
last(Bag,Last),
writeln( (N,Last) ) )).

% 1,724,404 inferences, 1.072 CPU in 1.151 seconds (93% CPU, 1607873 Lips)
Bag = [2, 3, 5, 7, 11, 13, 17, 19, 23|...],
N = 9592,
Last = 99991.

?-  time( prime(99991) ).
% 165 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 1213235 Lips)
true.

?-```

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 #TrueEndProcedure`

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`

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

Qi

`(define prime?-0  K N -> true where (> (* K K) N)  K N -> false where (= 0 (MOD N K))  K N -> (prime?-0 (+ K 2) N)) (define prime?  1 -> false  2 -> true  N -> false where (= 0 (MOD N 2))  N -> (prime?-0 3 N))`

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

Racket

`#lang racket (define (prime? number)  (cond ((not (positive? number)) #f)        ((= 1 number) #f)        ((even? number) (= 2 number))        (else (for/and ((i (in-range 3 (ceiling (sqrt number)))))                (not (zero? (remainder number i)))))))`

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        ]    ]]`
`repeat i 100 [ print [i prime? i]]`

REXX

compact version

This version uses a technique which increments by six for testing primality   (up to the   √ n ).

Programming note:   all the REXX programs below show all primes up and including the number specified.

If the number is negative, the absolute value of it is used for the upper limit, but no primes are shown.
The   number   of primes found is always shown.

Also, it was determined that computing the (integer) square root of the number to be tested in the   isPrime
function slowed up the function   (for all three REXX versions),   however, for larger numbers of   N,   it would
be faster.

`/*REXX program tests for  primality by using  (kinda smartish)  trial division.         */parse arg n .;  if n==''  then n=10000           /*let the user choose the upper limit. */tell=(n>0);     n=abs(n)                         /*display the primes  only if   N > 0. */p=0                                              /*a count of the primes found (so far).*/      do j=-57  to n                             /*start in the cellar and work up.     */      if \isPrime(j)  then iterate               /*if not prime,  then keep looking.    */      p=p+1                                      /*bump the jelly bean counter.         */      if tell  then say right(j,20) 'is prime.'  /*maybe display prime to the terminal. */      end   /*j*/saysay  "There are "      p       " primes up to "        n        ' (inclusive).'exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/isPrime: procedure;    parse arg x                       /*get the number to be tested. */         if wordpos(x, '2 3 5 7')\==0  then return 1     /*is number a teacher's pet?   */         if x<2 | x//2==0 | x//3==0    then return 0     /*weed out the riff-raff.      */            do k=5  by  6  until k*k>x                   /*skips odd multiples of  3.   */            if x//k==0 | x//(k+2)==0   then return 0     /*a pair of divides.      ___  */            end   /*k*/                                  /*divide up through the  √ x   */                                                         /*Note:  //   is  ÷  remainder.*/         return 1                                        /*done dividing, it's prime.   */`
output   when using the default input of:   100
```                   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 are  25  primes up to  100 (inclusive).```

optimized version

This version separates multiple-clause   if   statements, and also tests for low primes,

`/*REXX program tests for  primality by using  (kinda smartish)  trial division.         */parse arg n .;  if n==''  then n=10000           /*let the user choose the upper limit. */tell=(n>0);     n=abs(n)                         /*display the primes  only if   N > 0. */p=0                                              /*a count of the primes found (so far).*/      do j=-57  to n                             /*start in the cellar and work up.     */      if \isPrime(j)  then iterate               /*if not prime,  then keep looking.    */      p=p+1                                      /*bump the jelly bean counter.         */      if tell  then say right(j,20) 'is prime.'  /*maybe display prime to the terminal. */      end   /*j*/saysay  "There are "      p       " primes up to "        n        ' (inclusive).'exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/isPrime: procedure;  parse arg x                       /*get integer to be investigated.*/         if x<11     then return wordpos(x, '2 3 5 7')\==0         /*is it a wee prime? */         if x//2==0  then return 0                     /*eliminate all the even numbers.*/         if x//3==0  then return 0                     /* ··· and eliminate the triples.*/                  do k=5  by 6  until k*k>x            /*this skips odd multiples of 3. */                  if x//k    ==0  then return 0        /*perform a divide (modulus),    */                  if x//(k+2)==0  then return 0        /* ··· and the next umpty one.   */                  end   /*k*/                          /*Note: REXX  //  is ÷ remainder.*/         return 1                                      /*did all divisions, it's prime. */`
output   is identical to the first version when the same input is used.

unrolled version

This version uses an unrolled version (of the 2nd version) of some multiple-clause   if   statements, and
also an optimized version of the testing of low primes is used, making it about 22% faster.

Note that the   do ... until ...   was changed to   do ... while ....

`/*REXX program tests for  primality by using  (kinda smartish)  trial division.         */parse arg n .;  if n==''  then n=10000           /*let the user choose the upper limit. */tell=(n>0);     n=abs(n)                         /*display the primes  only if   N > 0. */p=0                                              /*a count of the primes found (so far).*/      do j=-57  to n                             /*start in the cellar and work up.     */      if \isPrime(j)  then iterate               /*if not prime,  then keep looking.    */      p=p+1                                      /*bump the jelly bean counter.         */      if tell  then say right(j,20) 'is prime.'  /*maybe display prime to the terminal. */      end   /*j*/saysay  "There are "      p       " primes up to "        n        ' (inclusive).'exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/isPrime: procedure;    parse arg x               /*get the integer to be investigated.  */         if x<107  then return wordpos(x, '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 101 103')\==0  /*some low primes.*/         if x// 2 ==0  then return 0             /*eliminate all the even numbers.      */         if x// 3 ==0  then return 0             /* ··· and eliminate the triples.      */         parse var  x  ''  -1  _                 /*          obtain the rightmost digit.*/         if     _ ==5  then return 0             /* ··· and eliminate the nickels.      */         if x// 7 ==0  then return 0             /* ··· and eliminate the luckies.      */         if x//11 ==0  then return 0         if x//13 ==0  then return 0         if x//17 ==0  then return 0         if x//19 ==0  then return 0         if x//23 ==0  then return 0         if x//29 ==0  then return 0         if x//31 ==0  then return 0         if x//37 ==0  then return 0         if x//41 ==0  then return 0         if x//43 ==0  then return 0         if x//47 ==0  then return 0         if x//53 ==0  then return 0         if x//59 ==0  then return 0         if x//61 ==0  then return 0         if x//67 ==0  then return 0         if x//71 ==0  then return 0         if x//73 ==0  then return 0         if x//79 ==0  then return 0         if x//83 ==0  then return 0         if x//89 ==0  then return 0         if x//97 ==0  then return 0         if x//101==0  then return 0         if x//103==0  then return 0             /*Note:  REXX   //   is  ÷  remainder. */                   do k=107  by 6  while k*k<=x  /*this skips odd multiples of three.   */                   if x//k    ==0  then return 0 /*perform a divide (modulus),          */                   if x//(k+2)==0  then return 0 /* ··· and the next also.   ___        */                   end   /*k*/                   /*divide up through the    √ x         */         return 1                                /*after all that,  ··· it's a prime.   */`
output   is identical to the first version when the same input is used.

Ring

`give n flag = isPrime(n)if flag = 1 see n + " is a prime number" else see n + " is not a prime number" ok func isPrime num     if (num <= 1) return 0 ok     if (num % 2 = 0 and num != 2) return 0 ok     for i = 3 to floor(num / 2) -1 step 2         if (num % i = 0) return 0 ok     next     return 1`

Ruby

`def prime(a)  if a == 2    true  elsif a <= 1 || a % 2 == 0    false  else    divisors = (3..Math.sqrt(a)).step(2)    divisors.none? { |d| a % d == 0 }  endendp (1..50).select{|i| prime(i)}`

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

`require "prime"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  endendp (1..50).select{|i| prime?(i)}`

Without any fancy stuff:

`def primes(limit)  (enclose = lambda { |primes|    primes.last.succ.upto(limit) do |trial_pri|      if primes.none? { |pri| (trial_pri % pri).zero? }        return enclose.call(primes << trial_pri)      end    end    primes  }).call([2])endp primes(50)`
Output:
```[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
```

By Regular Expression

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

Run BASIC

`' Test and display primes 1 .. 50for i = 1 TO 50  if prime(i) <> 0 then print i;" ";next i FUNCTION prime(n)if n < 2         then prime = 0 : goto [exit]if n = 2         then prime = 1 : goto [exit]if n mod 2 = 0   then prime = 0 : goto [exit]prime = 1for i = 3 to int(n^.5) step 2 if n mod i = 0 then  prime = 0 : goto [exit]next i[exit]END FUNCTION`
```2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49
```

Rust

`fn is_prime(n: u64) -> bool {    match n {        0 | 1 => false,        2 => true,        _even if n % 2 == 0 => false,        _ => {            let sqrt_limit = (n as f64).sqrt() as u64;            (3..=sqrt_limit).step_by(2).find(|i| n % i == 0).is_none()        }    }} fn main() {    for i in 1..30 {        if is_prime(i) {            println!("{} is prime!", i);        }    }}`
Output:
```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!```

S-lang

`define is_prime(n){   if (n == 2) return(1);   if (n <= 1) return(0);   if ((n & 1) == 0) return(0);    variable mx = int(sqrt(n)), i;    _for i (3, mx, 1) {     if ((n mod i) == 0)       return(0);   }   return(1);} define ptest() {   variable lst = {};    _for \$1 (1, 64, 1)     if (is_prime(\$1))       list_append(lst, string(\$1));   print(strjoin(list_to_array(lst), ", "));}ptest();`
Output:
```"2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61"
```

SAS

`data primes;do n=1 to 1000;  link primep;  if primep then output;end;stop; primep:if n < 4 then do;  primep=n=2 or n=3;  return;end;primep=0;if mod(n,2)=0 then return;do k=3 to sqrt(n) by 2;  if mod(n,k)=0 then return;end;primep=1;return;keep n;run;`

Scala

Simple version

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

Accelerated version FP and parallel runabled

//
Output:
Best seen running in your browser Scastie (remote JVM).
`object IsPrimeTrialDivision extends App {  def isPrime(n: Long) =    n > 1 && ((n & 1) != 0 || n == 2) && (n % 3 != 0 || n == 3) &&      (5 to math.sqrt(n).toInt by 6).par.forall(d => n % d != 0 && n % (d + 2) != 0)   assert(!isPrime(-1))  assert(!isPrime(1))  assert(isPrime(2))  assert(isPrime(100000000003L))  assert(isPrime(100000000019L))  assert(isPrime(100000000057L))  assert(isPrime(100000000063L))  assert(isPrime(100000000069L))  assert(isPrime(100000000073L))  assert(isPrime(100000000091L))  println("10 Numbers tested. A moment please …\nNumber crunching biggest 63-bit prime …")  assert(isPrime(9223372036854775783L)) // Biggest 63-bit prime  println("All done") }`

Accelerated version FP, tail recursion

Tests 1.3 M numbers against OEIS prime numbers.

`import scala.annotation.tailrecimport scala.io.Source object PrimesTestery extends App {  val rawText = Source.fromURL("https://oeis.org/A000040/a000040.txt")  val oeisPrimes = rawText.getLines().take(100000).map(_.split(" ")(1)).toVector   def isPrime(n: Long) = {    @tailrec    def inner(d: Int, end: Int): Boolean = {      if (d > end) true      else if (n % d != 0 && n % (d + 2) != 0) inner(d + 6, end) else false    }     n > 1 && ((n & 1) != 0 || n == 2) &&      (n % 3 != 0 || n == 3) && inner(5, math.sqrt(n).toInt)  }   println(oeisPrimes.size)  for (i <- 0 to 1299709) assert(isPrime(i) == oeisPrimes.contains(i.toString), s"Wrong \$i") }`

Scheme

Works with: Scheme version R${\displaystyle ^{5}}$RS
`(define (prime? number)  (define (*prime? divisor)    (or (> (* divisor divisor) number)        (and (> (modulo number divisor) 0)             (*prime? (+ divisor 1)))))  (and (> number 1)       (*prime? 2)))`
`; twice faster, testing only odd divisors(define (prime? n)  (if (< n 4) (> n 1)      (and (odd? n)	   (let loop ((k 3))	     (or (> (* k k) n)		 (and (positive? (remainder n k))		      (loop (+ k 2))))))))`

Seed7

`const func boolean: isPrime (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 odd(number) and number > 2 then      upTo := sqrt(number);      while number rem testNum <> 0 and testNum <= upTo do        testNum +:= 2;      end while;      prime := testNum > upTo;    end if;  end func;`

Original source: [3]

Sidef

`func is_prime(a) {  given (a) {    when (2)                   { true  }    case (a <= 1 || a.is_even) { false }    default                    { 3 .. a.isqrt -> any { .divides(a) } -> not }  }}`
Translation of: Perl

Alternative version, excluding multiples of 2 and 3:

`func is_prime(n) {    return (n >= 2) if (n < 4)    return false if (n%%2 || n%%3)    for k in (5 .. n.isqrt -> by(6)) {        return false if (n%%k || n%%(k+2))    }    return true}`

Smalltalk

`| isPrime |isPrime := [:n |    n even ifTrue: [ ^n=2 ]    ifFalse: [        3 to: n sqrt do: [:i |            (n \\ i = 0) ifTrue: [ ^false ]        ].        ^true    ]]`

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 = 1isp1    i = le(i + 2,max) i + 2 :f(return)        eq(remdr(n,i),0) :s(freturn)f(isp1)isprime_end`

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 .. 50loop    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
```

SQL

Works with: T-SQL
`declare @number intset @number = 514229 -- number to check ;with cte(number) as ( select 2 union all select number+1 from cte where number+1 < @number)select      cast(@number as varchar(100)) +      case           when exists				  (					select * 					from 					(						select number, @number % number modNumber						from cte					) tmp					where tmp.modNumber = 0 				  ) 				          then ' is composite'		  else						 ' is prime'	  end primalityTestoption (maxrecursion 0)`

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`

Swift

`import Foundation extension Int {  func isPrime() -> Bool {     switch self {    case let x where x < 2:      return false    case 2:      return true    default:      return        self % 2 != 0 &&        !stride(from: 3, through: Int(sqrt(Double(self))), by: 2).contains {self % \$0 == 0}    }  }}`

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

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

uBasic/4tH

`10 LET n=0: LET p=020 INPUT "Enter number: ";n30 LET p=0 : IF n>1 THEN GOSUB 100040 IF p=0 THEN PRINT n;" is not prime!"50 IF p#0 THEN PRINT n;" is prime!"60 GOTO 101000 REM ***************1001 REM * PRIME CHECK *1002 REM ***************1010 LET p=01020 IF (n%2)=0 THEN RETURN1030 LET p=1 : PUSH n,0 : GOSUB 90301040 FOR i=3 TO POP() STEP 21050 IF (n%i)=0 THEN LET p=0: PUSH n,0 : GOSUB 9030 : LET i=POP()1060 NEXT i1070 RETURN9030 Push ((10^(Pop()*2))*Pop()) : @(255)=Tos()9040 Push (@(255) + (Tos()/@(255)))/2     If Abs(@(255)-Tos())<2 Then @(255)=Pop() : If Pop() Then Push @(255) : Return     @(255) = Pop() : Goto 9040     REM ** This is an integer SQR subroutine. Output is scaled by 10^(TOS()).`

UNIX Shell

Translation of: C
Works with: bash
Works with: ksh93
Works with: pdksh
Works with: zsh
`function primep {	typeset n=\$1 p=3	(( n == 2 )) && return 0	# 2 is prime.	(( n & 1 )) || return 1		# Other evens are not prime.	(( n >= 3 )) || return 1 	# Loop for odd p from 3 to sqrt(n).	# Comparing p * p <= n can overflow.	while (( p <= n / p )); do		# If p divides n, then n is not prime.		(( n % p )) || return 1		(( p += 2 ))	done	return 0	# Yes, n is prime.}`
Works with: Bourne Shell
`primep() {	set -- "\$1" 3	test "\$1" -eq 2 && return 0		# 2 is prime.	expr "\$1" \% 2 >/dev/null || return 1	# Other evens are not prime.	test "\$1" -ge 3 || return 1 	# Loop for odd p from 3 to sqrt(n).	# Comparing p * p <= n can overflow. We use p <= n / p.	while expr \$2 \<= "\$1" / \$2 >/dev/null; do		# If p divides n, then n is not prime.		expr "\$1" % \$2 >/dev/null || return 1		set -- "\$1" `expr \$2 + 2`	done	return 0	# Yes, n is prime.}`

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/~& [email protected]`

Test program to try it on a few numbers:

`#cast %bL test = prime* <5,6,7>`
Output:
```<true,false,true>
```

V

Translation of: Joy
`[prime?     2     [[dup * >] [true] [false] ifte [% 0 >] dip and]       [succ]     while     dup * <].`
Using it:
`|11 prime?=true|4 prime?=false`

VBA

`Option Explicit Sub FirstTwentyPrimes()Dim count As Integer, i As Long, t(19) As String   Do      i = i + 1      If IsPrime(i) Then         t(count) = i         count = count + 1      End If   Loop While count <= UBound(t)   Debug.Print Join(t, ", ")End Sub Function IsPrime(Nb As Long) As Boolean   If Nb = 2 Then      IsPrime = True   ElseIf Nb < 2 Or Nb Mod 2 = 0 Then      Exit Function   Else      Dim i As Long      For i = 3 To Sqr(Nb) Step 2         If Nb Mod i = 0 Then Exit Function      Next      IsPrime = True   End IfEnd Function`
Output:
```2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
```

VBScript

Translation of: BASIC
`Function IsPrime(n)	If n = 2 Then		IsPrime = True	ElseIf n <= 1 Or n Mod 2 = 0 Then		IsPrime = False	Else		IsPrime = True		For i = 3 To Int(Sqr(n)) Step 2			If n Mod i = 0 Then				IsPrime = False				Exit For			End If		Next	End IfEnd Function For n = 1 To 50	If IsPrime(n) Then		WScript.StdOut.Write n & " "	End IfNext`
Output:
```2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
```

XPL0

`include c:\cxpl\codes;  \intrinsic 'code' declarations func Prime(N);          \Return 'true' if N is a prime numberint  N;int  I;[if N <= 1 then return false;for I:= 3 to sqrt(N) do        if rem(N/I) = 0 then return false;return true;]; \Prime int  Num;repeat  Num:= IntIn(0);        Text(0, if Prime(Num) then "is " else "not ");        Text(0, "prime^M^J");until   Num = 0`
Output:
```777777777
not prime
777777773
is prime
0
not prime```

zkl

The Method filter1 stops at the first non False result, which, if there is one, is the first found diviser, thus short cutting the rest of the test

`fcn isPrime(n){   if(n.isEven or n<2) return(n==2);    (not [3..n.toFloat().sqrt().toInt(),2].filter1('wrap(m){n%m==0}))}`
Output:
```zkl: [1..].filter(20,isPrime)
L(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71)
zkl: isPrime(777777773)
True
zkl: isPrime(777777777)
False```