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 greater than   2   may be eliminated right away.

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

11l

```F is_prime(n)
I n < 2
R 0B
L(i) 2..Int(sqrt(n))
I n % i == 0
R 0B
R 1B```

360 Assembly

```*        Primality by trial division  26/03/2017
PRIMEDIV CSECT
USING  PRIMEDIV,R13       base register
B      72(R15)            skip savearea
DC     17F'0'             savearea
STM    R14,R12,12(R13)    save previous context
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' '            buffer
XDEC     DS     CL12               temp for xdeco
YREGS
END    PRIMEDIV```
Output:
```  2   3   5   7  11  13  17  19  23  29  31  37  41  43  47
```

68000 Assembly

```isPrime:
; REG USAGE:
; D0 = input (unsigned 32-bit integer)
; D1 = temp storage for D0
; D2 = candidates for possible factors
; D3 = temp storage for quotient/remainder
; D4 = total count of proper divisors.

MOVEM.L D1-D4,-(SP)      ;push data regs except D0
MOVE.L #0,D1
MOVEM.L D1,D2-D4         ;clear regs D1 thru D4

CMP.L #0,D0
BEQ notPrime
CMP.L #1,D0
BEQ notPrime
CMP.L #2,D0
BEQ wasPrime

MOVE.L D0,D1            ;D1 will be used for temp storage.
AND.L #1,D1             ;is D1 even?
BEQ notPrime            ;if so, it's not prime!

MOVE.L D0,D1            ;restore D1

computeFactors:
DIVU D2,D1              ;remainder is in top 2 bytes, quotient in bottom 2.
MOVE.L D1,D3		;temporarily store into D3 to check the remainder
SWAP D3			;swap the high and low words of D3. Now bottom 2 bytes contain remainder.
CMP.W #0,D3		;is the bottom word equal to 0?
BNE D2_Wasnt_A_Divisor	;if not, D2 was not a factor of D1.

ADDQ.L #1,D4            ;increment the count of proper divisors.
CMP.L #2,D4             ;is D4 two or greater?
BCC notPrime            ;if so, it's not prime! (Ends early. We'll need to check again if we made it to the end.)

D2_Wasnt_A_Divisor:
MOVE.L D0,D1            ;restore D1.

CMP.L D2,D1             ;is D2 now greater than D1?
BLS computeFactors      ;if not, loop again

CMP.L #1,D4		;was there only one factor?
BEQ wasPrime		;if so, D0 was prime.

notPrime:
MOVE.L #0,D0             ;return false
MOVEM.L (SP)+,D1-D4      ;pop D1-D4
RTS

wasPrime:
MOVE.L #1,D0             ;return true
MOVEM.L (SP)+,D1-D4      ;pop D1-D4
RTS
;end of program
```

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
```/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program testPrime64.s   */

/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

/*******************************************/
/* Initialized data */
/*******************************************/
.data
szMessStartPgm:            .asciz "Program start \n"
szMessEndPgm:              .asciz "Program normal end.\n"
szMessNotPrime:            .asciz "Not prime.\n"
szMessPrime:               .asciz "Prime\n"
szCarriageReturn:          .asciz "\n"

/*******************************************/
/* UnInitialized data                      */
/*******************************************/
.bss
.align 4
/*******************************************/
/*  code section                           */
/*******************************************/
.text
.global main
main:                                           // program start
ldr x0,qAdrszMessStartPgm                   // display start message
bl affichageMess
ldr x0,qVal
bl isPrime                                  // test prime ?
cmp x0,#0
beq 1f
bl affichageMess
b 2f
1:
bl affichageMess
2:

ldr x0,qAdrszMessEndPgm                     // display end message
bl affichageMess

100:                                            // standard end of the program
mov x0,0                                    // return code
mov x8,EXIT                                 // request to exit program
svc 0                                       // perform system call
//qVal:                      .quad 1042441       // test not prime
//qVal:                      .quad 1046527       // test prime
//qVal:                       .quad 37811          // test prime
//qVal:                      .quad 1429671721    // test not prime (37811 * 37811)
qVal:                      .quad 100000004437    // test prime
/******************************************************************/
/*     test if number is prime                                    */
/******************************************************************/
/* x0 contains the number  */
/* x0 return 1 if prime else return 0 */
isPrime:
stp x1,lr,[sp,-16]!        // save  registers
cmp x0,1                   // <= 1 ?
ble 98f
cmp x0,3                   // 2 and 3 prime
ble 97f
tst x0,1                   //  even ?
beq 98f
mov x11,3                 // first divisor
1:
udiv x12,x0,x11
msub x13,x12,x11,x0       // compute remainder
cbz x13,98f               // end if zero
cmp x11,x12               // divisors<=quotient ?
ble 1b                    // loop
97:
mov x0,1                  // return prime
b 100f
98:
mov x0,0                  // not prime
b 100f
100:
ldp x1,lr,[sp],16         // restaur  2 registers

/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"```

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

Action!

```BYTE FUNC IsPrime(CARD a)
CARD i

IF a<=1 THEN
RETURN (0)
FI

FOR i=2 TO a/2
DO
IF a MOD i=0 THEN
RETURN (0)
FI
OD
RETURN (1)

PROC Test(CARD a)
IF IsPrime(a) THEN
PrintF("%I is prime%E",a)
ELSE
PrintF("%I is not prime%E",a)
FI
RETURN

PROC Main()
Test(13)
Test(997)
Test(1)
Test(6)
Test(120)
Test(0)
RETURN```
Output:
```13 is prime
997 is prime
1 is not prime
6 is not prime
120 is not prime
0 is not prime
```

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
Test : Natural;
begin
if Item = 1 then
return False;
elsif Item = 2 then
return True;
elsif Item mod 2 = 0 then
return False;
else
Test := 3;
while Test <= Integer(Sqrt(Float(Item))) loop
if Item mod Test = 0 then
return False;
end if;
Test := Test + 2;
end loop;
end if;
return True;
end Is_Prime;
```

`Sqrt` is made visible by a with / use clause on `Ada.Numerics.Elementary_Functions`.

With Ada 2012, the function can be made more compact as an expression function (but without loop optimized by skipping even numbers) :

```function Is_Prime(Item : Positive) return Boolean is
(Item /= 1 and then
(for all Test in 2..Integer(Sqrt(Float(Item))) => Item mod Test /= 0));
```

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 60

Works with: A60
```begin

boolean procedure isprime(n);
value n; integer n;
begin
comment - local procedure tests whether n is even;
boolean procedure even(n);
value n; integer n;
even := entier(n / 2) * 2 = n;

if n < 2 then
isprime := false
else if even(n) then
isprime := (n = 2)
else
begin
comment - check odd divisors up to sqrt(n);
integer i, limit;
boolean divisible;
i := 3;
limit := entier(sqrt(n));
divisible := false;
for i := i while i <= limit and not divisible do
begin
if entier(n / i) * i = n then
divisible := true;
i := i + 2
end;
isprime := if divisible then false else true;
end;
end;

comment - exercise the procedure;
integer i;
outstring(1,"Testing first 50 numbers for primality:\n");
for i := 1 step 1 until 50 do
if isprime(i) then
outinteger(1,i);

end```
Output:
```Testing first 50 numbers for primality:
2  3  5  7  11  13  17  19  23  29  31  37  41  43  47
```

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

```BEGIN

% RETURN P MOD Q %
INTEGER FUNCTION MOD(P, Q);
INTEGER P, Q;
BEGIN
MOD := P - Q * (P / Q);
END;

% RETURN INTEGER SQUARE ROOT OF N %
INTEGER FUNCTION ISQRT(N);
INTEGER N;
BEGIN
INTEGER R1, R2;
R1 := N;
R2 := 1;
WHILE R1 > R2 DO
BEGIN
R1 := (R1+R2) / 2;
R2 := N / R1;
END;
ISQRT := R1;
END;

% RETURN 1 IF N IS PRIME, OTHERWISE 0 %
INTEGER FUNCTION ISPRIME(N);
INTEGER N;
BEGIN
IF N = 2 THEN
ISPRIME := 1
ELSE IF (N < 2) OR (MOD(N,2) = 0) THEN
ISPRIME := 0
ELSE % TEST ODD NUMBERS UP TO SQRT OF N %
BEGIN
INTEGER I, LIMIT;
LIMIT := ISQRT(N);
I := 3;
WHILE I <= LIMIT AND MOD(N,I) <> 0 DO
I := I + 2;
ISPRIME := (IF I <= LIMIT THEN 0 ELSE 1);
END;
END;

% TEST FOR PRIMES IN RANGE 1 TO 50 %
INTEGER I;
WRITE("");
FOR I := 1 STEP 1 UNTIL 50 DO
BEGIN
IF ISPRIME(I)=1 THEN WRITEON(I,"  "); % WORKS FOR 80 COL SCREEN %
END;

END```
Output:
```     2       3       5       7      11      13      17      19      23      29
31      37      41      43      47
```

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

AppleScript

```on isPrime(n)
if (n < 3) then return (n is 2)
if (n mod 2 is 0) then return false
repeat with i from 3 to (n ^ 0.5) div 1 by 2
if (n mod i is 0) then return false
end repeat

return true
end isPrime

-- Test code:
set output to {}
repeat with n from -7 to 100
if (isPrime(n)) then set end of output to n
end repeat
return output
```

Or eliminating multiples of 3 at the start as well as those of 2:

```on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
repeat with i from 5 to (n ^ 0.5) div 1 by 6
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
end repeat

return true
end isPrime

-- Test code:
set output to {}
repeat with n from -7 to 100
if (isPrime(n)) then set end of output to n
end repeat
return output
```
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}
```

Arturo

```isPrime?: function [n][
if n=2 -> return true
if n=3 -> return true
if or? n=<1 0=n%2 -> return false

high: to :integer sqrt n
loop high..2 .step: 3 'i [
if 0=n%i -> return false
]

return true
]

loop 1..20 'i [
print ["isPrime?" i "=" isPrime? i ]
]
```
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
isPrime? 16 = false
isPrime? 17 = true
isPrime? 18 = false
isPrime? 19 = true
isPrime? 20 = false```

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
Next
EndFunc

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 True
EndFunc
main()
```

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

B

B as on PDP7/UNIX0

Translation of: C
Works with: B as on PDP7/UNIX0 version (proto-B?)
```isprime(n) {
auto p;
if(n<2) return(0);
if(!(n%2)) return(n==2);
p=3;
while(n/p>p) {
if(!(n%p)) return(0);
p=p+2;
}
return(1);
}```

BASIC

Works with: QBasic version 1.1
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
```

IS-BASIC

```100 PROGRAM "Prime.bas"
110 FOR X=0 TO 100
120   IF PRIME(X) THEN PRINT X;
130 NEXT
140 DEF PRIME(N)
150   IF N=2 THEN
160     LET PRIME=-1
170   ELSE IF N<=1 OR MOD(N,2)=0 THEN
180     LET PRIME=0
190   ELSE
200     LET PRIME=-1
210     FOR I=3 TO CEIL(SQR(N)) STEP 2
220       IF MOD(N,I)=0 THEN LET PRIME=0:EXIT FOR
230     NEXT
240   END IF
250 END DEF```

True BASIC

Translation of: BASIC
```FUNCTION isPrime (n)
IF n = 2 THEN
LET isPrime = 1
ELSEIF n <= 1 OR REMAINDER(n, 2) = 0 THEN
LET isPrime = 0
ELSE
LET isPrime = 1
FOR i = 3 TO INT(SQR(n)) STEP 2
IF REMAINDER(n, i) = 0 THEN
LET isPrime = 0
EXIT FUNCTION
END IF
NEXT i
END IF
END FUNCTION

FOR n = 1 TO 50
IF isPrime(n) = 1 THEN PRINT n;
NEXT n
END
```

ZX Spectrum Basic

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

BASIC256

Translation of: FreeBASIC
```for i = 1 to 99
if isPrime(i) then print string(i); " ";
next i
end

function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
```

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

BCPL

```get "libhdr"

let sqrt(s) =
s <= 1 -> 1,
valof
\$(  let x0 = s >> 1
let x1 = (x0 + s/x0) >> 1
while x1 < x0
\$(  x0 := x1
x1 := (x0 + s/x0) >> 1
\$)
resultis x0
\$)

let isprime(n) =
n < 2       -> false,
(n & 1) = 0 -> n = 2,
valof
\$(  for i = 3 to sqrt(n) by 2
if n rem i = 0 resultis false
resultis true
\$)

let start() be
\$(  for i=1 to 100
if isprime(i) then writef("%N ",i)
wrch('*N')
\$)```
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`

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`!#^_2v
v_v#`\*:%*:*84\/*:*84::+<
v >::48*:*/\48*:*%%!#v_1^
>0"seY" >:#,_@#: "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```

Brainf***

```>->,[.>,]>-<++++++[-<+[---------<+]->+[->+]-<]>+<-<+[-<+]>>+[-<[->++++++++++<]>>
+]++++[->++++++++<]>.<+++++++[->++++++++++<]>+++.++++++++++.<+++++++++[->-------
--<]>--.[-]<<<->[->+>+<<]>>-[+<[[->>+>>+<<<<]>>[-<<+>>]<]>>[->-[>+>>]>[+[-<+>]>>
>]<<<<<]>[-]>[>+>]<<[-]+[-<+]->>>--]<[->+>+<<]>>>>>>>[-<<<<<->>>>>]<<<<<--[>++++
++++++[->+++++++++++<]>.+.+++++.>++++[->++++++++<]>.>]++++++++++[->+++++++++++<]
>++.++.---------.++++.--------.>++++++++++.
```

Explanation:

```>
->,[.>,]>-<++++++[-<+[---------<+]->+[->+]-<]>+<-<+[-<+]>>+[-<[->++++++++++<]>>+]<                     takes input
>++++[->++++++++<]>.<+++++++[->++++++++++<]>+++.++++++++++.<+++++++++[->---------<]>--.[-]<<           " is "
<->
[->+>+<<]>>-[+<[[->>+>>+<<<<]>>[-<<+>>]<]>>[->-[>+>>]>[+[-<+>]>>>]<<<<<]>[-]>[>+>]<<[-]+[-<+]->>>--]   finds # of divisors from 1 to n
<[->+>+<<]>>>>>>>[-<<<<<->>>>>]<<<<<--
[>++++++++++[->+++++++++++<]>.+.+++++.>++++[->++++++++<]>.>]                                           "not "
++++++++++[->+++++++++++<]>++.++.---------.++++.--------.>++++++++++.                                  "prime" new line
```

Will format as "# is/is not prime", naturally limited by cell size.

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\/?dr@.%{0==}ayn!
1
blsq ) 12^^2\/?dr@.%{0==}ayn!
0
blsq ) 13^^2\/?dr@.%{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#

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

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

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)
(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]
(and (integer? x)
(< 1 x)
(not-any? (partial divides? x)
(take-while (partial >= (Math/sqrt x)) primes))))
```

CLU

```isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0=0 then return(s) end
x1: int := (x0 + s/x0)/2
while x1 < x0 do
x0 := x1
x1 := (x0 + s/x0)/2
end
return(x0)
end isqrt

prime = proc (n: int) returns (bool)
if n<=2 then return(n=2) end
if n//2=0 then return(false) end
for d: int in int\$from_to_by(3,isqrt(n),2) do
if n//d=0 then return(false) end
end
return(true)
end prime

start_up = proc ()
po: stream := stream\$primary_input()
for i: int in int\$from_to(1,100) do
if prime(i) then
stream\$puts(po, int\$unparse(i) || " ")
end
end
end start_up```
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`

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

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

Crystal

```Mathematicaly basis of Prime Generators
```
```require "big"
require "benchmark"

# the simplest PG primality test using the P3 prime generator
# reduces the number space for primes to 2/6 (33.33%) of all integers

def primep3?(n)                           # P3 Prime Generator primality test
# P3 = 6*k + {5, 7}                     # P3 primes candidates (pc) sequence
n = n.to_big_i
return n | 1 == 3 if n < 5              # n: 0,1,4|false, 2,3|true
return false if n.gcd(6) != 1           # 1/3 (2/6) of integers are P3 pc
p = typeof(n).new(5)                    # first P3 sequence value
until p > isqrt(n)
return false if n % p == 0 || n % (p + 2) == 0  # if n is composite
p += 6      # first prime candidate for next kth residues group
end
true
end

# PG primality test using the P5 prime generator
# reduces the number space for primes to 8/30 (26.67%) of all integers

def primep5?(n)                          # P5 Prime Generator primality test
# P5 = 30*k + {7,11,13,17,19,23,29,31} # P5 primes candidates sequence
n = n.to_big_i
return [2, 3, 5].includes?(n) if n < 7 # for small and negative values
return false if n.gcd(30) != 1         # 4/15 (8/30) of integers are P5 pc
p = typeof(n).new(7)                   # first P5 sequence value
until p > isqrt(n)
return false if                      # if n is composite
n % (p)    == 0 || n % (p+4)  == 0 || n % (p+6)  == 0 || n % (p+10) == 0 ||
n % (p+12) == 0 || n % (p+16) == 0 || n % (p+22) == 0 || n % (p+24) == 0
p += 30  # first prime candidate for next kth residues group
end
true
end

# PG primality test using the P7 prime generator
# reduces the number space for primes to 48/210 (22.86%) of all integers

def primep7?(n)
# P7 = 210*k + {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,121,127,131,137,139,143,149,151,157,163,
#      167,169,173,179,181,187,191,193,197,199,209,211}
n = n.to_big_i
return [2, 3, 5, 7].includes?(n) if n < 11
return false if n.gcd(210) != 1         # 8/35 (48/210) of integers are P7 pc
p = typeof(n).new(11)                   # first P7 sequence value
until p > isqrt(n)
return false if
n % (p)     == 0 || n % (p+2)   == 0 || n % (p+6)   == 0 || n % (p+8)   == 0 ||
n % (p+12)  == 0 || n % (p+18)  == 0 || n % (p+20)  == 0 || n % (p+26)  == 0 ||
n % (p+30)  == 0 || n % (p+32)  == 0 || n % (p+36)  == 0 || n % (p+42)  == 0 ||
n % (p+48)  == 0 || n % (p+50)  == 0 || n % (p+56)  == 0 || n % (p+60)  == 0 ||
n % (p+62)  == 0 || n % (p+68)  == 0 || n % (p+72)  == 0 || n % (p+78)  == 0 ||
n % (p+86)  == 0 || n % (p+90)  == 0 || n % (p+92)  == 0 || n % (p+96)  == 0 ||
n % (p+98)  == 0 || n % (p+102) == 0 || n % (p+110) == 0 || n % (p+116) == 0 ||
n % (p+120) == 0 || n % (p+126) == 0 || n % (p+128) == 0 || n % (p+132) == 0 ||
n % (p+138) == 0 || n % (p+140) == 0 || n % (p+146) == 0 || n % (p+152) == 0 ||
n % (p+156) == 0 || n % (p+158) == 0 || n % (p+162) == 0 || n % (p+168) == 0 ||
n % (p+170) == 0 || n % (p+176) == 0 || n % (p+180) == 0 || n % (p+182) == 0 ||
n % (p+186) == 0 || n % (p+188) == 0 || n % (p+198) == 0 || n % (p+200) == 0
p += 210    # first prime candidate for next  kth residues group
end
true
end

# Newton's method for integer squareroot
def isqrt(n)
raise ArgumentError.new "Input must be non-negative integer" if n < 0
return n if n < 2
bits = n.bit_length
one = typeof(n).new(1)  # value 1 of type self
x = one << ((bits - 1) >> 1) | n >> ((bits >> 1) + 1)
while (t = n // x) < x; x = (x + t) >> 1 end
x   # output is same integer class as input
end

# Benchmarks to test for various size primes

p = 541
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
puts
end

p = 1000003
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
puts
end

p = 2147483647i32     # largest I32 prime
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
puts
end

p = 4294967291u32     # largest U32 prime
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
puts
end

p = 4294967311      # first prime > 2**32
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
puts
end
```
Output:
```p = 541
primep3? 290.17k (  3.45µs) (± 2.76%)  1.35kB/op   1.64× slower
primep5? 476.47k (  2.10µs) (± 1.75%)    802B/op        fastest
primep7? 128.44k (  7.79µs) (± 2.82%)  2.66kB/op   3.71× slower

p = 1000003
primep3?  11.24k ( 88.97µs) (± 2.34%)  33.9kB/op   2.48× slower
primep5?  21.91k ( 45.64µs) (± 2.88%)  16.6kB/op   1.27× slower
primep7?  27.83k ( 35.94µs) (± 2.68%)  11.9kB/op        fastest

p = 2147483647
primep3? 105.11  (  9.51ms) (± 3.25%)  3.89MB/op   5.56× slower
primep5? 317.49  (  3.15ms) (± 2.40%)   1.2MB/op   1.84× slower
primep7? 584.92  (  1.71ms) (± 3.09%)   591kB/op        fastest

p = 4294967291
primep3? 168.56  (  5.93ms) (± 2.39%)  2.17MB/op   2.69× slower
primep5? 349.24  (  2.86ms) (± 2.86%)  1.03MB/op   1.30× slower
primep7? 454.08  (  2.20ms) (± 2.62%)   739kB/op        fastest

p = 4294967311
primep3?  84.61  ( 11.82ms) (± 2.35%)  4.68MB/op   5.02× slower
primep5? 248.62  (  4.02ms) (± 2.21%)  1.54MB/op   1.71× slower
primep7? 424.61  (  2.36ms) (± 2.73%)   813kB/op        fastest
```

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

EasyLang

```func isPrime num . result\$ .
if num < 2
result\$ = "false"
break 1
.
if num mod 2 = 0 and num > 2
result\$ = "false"
break 1
.
for i = 3 to sqrt num
if num mod i = 0
result\$ = "false"
break 2
.
.
result\$ = "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

Library: cl-lib
```(defun prime (a)
(not (or (< a 2)
(cl-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)
(cl-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) (cl-oddp a))
(cl-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)
(cl-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) (cl-evenp a))
(cl-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%=TRUE
END 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 if
end function```

F#

```open NUnit.Framework
open FsUnit
let 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
```

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=\$[@~@@]?~[\$\$2>\1&&[\~\
3[\\$@\$@1+\\$*>][\\$@\$@\$@\$@\/*=[%\~\\$]?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 IF
END 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 TRUE
END FUNCTION

' Test and display primes 1 .. 50
DIM n AS INTEGER

FOR n = 1 TO 50
IF ISPRIME(n) THEN
PRINT n, " ";
END IF
NEXT

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 True
End Function

' To test this works, print all primes under 100
For i As Integer = 1 To 99
If isPrime(i) Then
Print Str(i); " ";
End If
Next

Print : Print
Print "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
```

Frink

It is unnecessary to write this function because Frink has an efficient `isPrime[x]` function to test primality of arbitrarily-large integers. Here is a version that works for arbitrarily-large integers. Beware some of these solutions that calculate up to `sqrt[x]` but because of floating-point error the square root is slightly smaller than the true square root!

```isPrimeByTrialDivision[x] :=
{
for p = primes[]
{
if p*p > x
return true
if x mod p == 0
return false
}

return true
}```

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

```window 1, @"Primality By Trial Division", (0,0,480,270)

local fn isPrime( n as long ) as Boolean
long    i
Boolean result

if n < 2 then result = NO : exit fn
if n = 2 then result = YES : exit fn
if n mod 2 == 0  then result = NO : exit fn

result = YES
for i = 3 to int( n^.5 ) step 2
if n mod i == 0 then result = NO : break
next i
end fn = result

long i, j = 0

print "Prime numbers between 0 and 1000:"
for i = 0 to 1000
if ( fn isPrime(i) != _false )
printf @"%3d\t",i : j++
if j mod 10 == 0 then print
end if
next

HandleEvents```

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 Boolean
Dim iLoop As Integer
Dim bReturn As Boolean = True

If iNum <= 1 Then bReturn = False
If iNum <= 3 Then bReturn = True
If (iNum And 1) = 0 Then bReturn = False

For iLoop = 3 To Sqr(iNum) Step 2
If iNum Mod iLoop = 0 Then bReturn = False
Next

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

Icon and Unicon

Procedure shown without a main program.

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

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

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

n = 100
a = 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'!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```

Kotlin

```// version 1.1.2
fun 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
```

Lambdatalk

```1) the simplest

{def isprime1
{def isprime1.loop
{lambda {:n :m :i}
{if {> :i :m}
then true
else {if {= {% :n :i} 0}
then false
else {isprime1.loop :n :m {+ :i 1}} }
}}}
{lambda {:n}
{isprime1.loop :n {sqrt :n} 2}
}}
-> isprime1

2) slightly improved

{def isprime2
{def isprime2.loop
{lambda {:n :m :i}
{if {> :i :m}
then true
else {if {= {% :n :i} 0}
then false
else {isprime2.loop :n :m {+ :i 2}}
}}}}
{lambda {:n}
{if {or {= :n 2} {= :n 3} {= :n 5} {= :n 7}}
then true
else {if {or {< : n 2} {= {% :n 2} 0}}
then false
else {isprime2.loop :n {sqrt :n} 3}
}}}}
-> isprime2

3) testing

{isprime1 1299709} -> stackoverflow on my iPad Pro
{isprime2 1299709} -> true

{def primesTo
{lambda {:f :n}
{S.replace \s by space in
{S.map {{lambda {:f :i} {if {:f :i} then :i else}} :f}
{S.serie 2 :n}}} }}
-> primesTo

{primesTo isprime1 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  in 25ms
{primesTo isprime2 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  in 20ms

{primesTo isprime1 1000000}  in about 30000ms
{primesTo isprime2 1000000}  in about 15000ms
```

langur

Recursive

Translation of: Go
Works with: langur version 0.11
```val .isPrime = f(.i) {
val .n = abs(.i)
if .n <= 2: return .n == 2

val .chkdiv = f(.n, .i) {
if .i x .i <= .n {
return .n ndiv .i and self(.n, .i+2)
}
return true
}

return .n ndiv 2 and .chkdiv(.n, 3)
}

writeln filter .isPrime, series 100```

Functional

Translation of: Raku

following the Raku example, which states, "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" (plus an adjustment for the prime number 2)

Below, we use an implied parameter (.i) on the .isPrime function.

Works with: langur version 0.11
```val .isPrime = f .i == 2 or
.i > 2 and not any f(.x) .i div .x, pseries 2 to .i ^/ 2

writeln filter .isPrime, series 100```
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: "; x
if x=0 then print "Program complete.": end
if 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=1
end 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 TRUE
end```
```primes = []
repeat with i = 0 to 100
end repeat
put 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 "true
end```

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

Type of number Decimal.

M2000 Interpreter

```      Inventory Known1=2@, 3@
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 = 5@
{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 if
end 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/Wolfram Language

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

min

Works with: min version 0.19.3
```(
:n 3 :i n sqrt :m true :p
(i m <=) (
(n i mod 0 ==) (m @i false @p) when
i 2 + @i
) while p
) :_prime?  ; helper function

(
(
((2 <) (false))
((dup even?) (2 ==))
((true) (_prime?))
) case
) :prime?```

МК-61/52

```П0	1	-	x#0	34	2	-	/-/	x<0	32
ИП0	2	/	{x}	x#0	34
3	П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
end
else 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

say
say "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!*/
```

newLISP

Short-circuit evaluation ensures that the many Boolean expressions are calculated in the right order so as not to waste time.

```; Here are some simpler functions to help us:

(define (divisible? larger-number smaller-number)
(zero? (% larger-number smaller-number)))

(define (int-root number)
(floor (sqrt number)))

(define (even-prime? number)
(= number 2))

; Trial division for odd numbers

(define (find-odd-factor? odd-number)
(catch
(for (possible-factor 3 (int-root odd-number) 2)
(if (divisible? odd-number possible-factor)
(throw true)))))

(define (odd-prime? number)
(and
(odd? number)
(or
(= number 3)
(and
(> number 3)
(not (find-odd-factor? number))))))

; Now for the final overall Boolean function.

(define (is-prime? possible-prime)
(or
(even-prime? possible-prime)
(odd-prime? possible-prime)))

; Let's use this to actually find some prime numbers.

(println (filter is-prime? (sequence 1 100)))
(exit)
```
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)

Nim

Here are three ways to test primality using trial division.

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

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)
```
Output:
```2 true
3 true
4 false
5 true
6 false
7 true
8 false
9 false
10 false
11 true
12 false
13 true
14 false
15 false
16 false
17 true
18 false
19 true
20 false
21 false
22 false
23 true
24 false
25 false
26 false
27 false
28 false
29 true
30 false```

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 =
let rec test x =
x * x > n || n mod x <> 0 && n mod (x + 2) <> 0 && test (x + 6)
in
if n < 5
then n lor 1 = 3
else n land 1 <> 0 && n mod 3 <> 0 && test 5
```

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

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

Ol

```(define (prime? number)
(define max (sqrt number))
(define (loop divisor)
(or (> divisor max)
(and (> (modulo number divisor) 0)
(loop (+ divisor 2)))))
(or (= number 1)
(= number 2)
(and
(> (modulo number 2) 0)
(loop 3))))
```

Testing:

```; first prime numbers less than 100
(for-each (lambda (n)
(if (prime? n)
(display n))
(display " "))
(iota 100))
(print)

; few more sintetic tests
(for-each (lambda (n)
(print n " - prime? " (prime? n)))
'(
1234567654321 ; 1111111 * 1111111
679390005787 ; really prime, I know that
679390008337 ; same
666810024403 ; 680633 * 979691 (multiplication of two prime numbers)
12345676543211234567654321
12345676543211234567654321123456765432112345676543211234567654321123456765432112345676543211234567654321
))
```
Output:
``` 1 2 3  5  7    11  13    17  19    23      29  31      37    41  43    47      53      59  61      67    71  73      79    83      89        97
1234567654321 - prime? #false
679390005787 - prime? #true
679390008337 - prime? #true
666810024403 - prime? #false
12345676543211234567654321 - prime? #false
12345676543211234567654321123456765432112345676543211234567654321123456765432112345676543211234567654321 - prime? #false
```

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

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

PARI/GP

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

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

improved using number wheel

Library: primTrial
Works with: Free Pascal
```program TestTrialDiv;
{\$IFDEF FPC}
{\$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";
```

Phix

```function is_prime_by_trial_division(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 1
end function
?filter(tagset(32),is_prime_by_trial_division)
```
Output:
```{2,3,5,7,11,13,17,19,23,29,31}
```

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

?>
```

By Regular Expression

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

Picat

Here are four different versions.

Iterative

```is_prime1(N) =>
if N == 2 then
true
elseif N <= 1 ; N mod 2 == 0 then
false
else
foreach(I in 3..2..ceiling(sqrt(N)))
N mod I > 0
end
end.```

Recursive

```is_prime2(N) =>
(N == 2 ; is_prime2b(N,3)).

is_prime2b(N,_Div), N <= 1 => false.
is_prime2b(2,_Div) => true.
is_prime2b(N,_Div), N mod 2 == 0 => false.
is_prime2b(N,Div), Div > ceiling(sqrt(N)) => true.
is_prime2b(N,Div), Div > 2 =>
(N mod Div == 0 ->
false
;
is_prime2b(N,Div+2)
).```

Functional

```is_prime3(2) => true.
is_prime3(3) => true.
is_prime3(P) => P > 3, P mod 2 =\= 0, not has_factor3(P,3).

has_factor3(N,L), N mod L == 0 => true.
has_factor3(N,L) => L * L < N, L2 = L + 2, has_factor3(N,L2).```

Generator approach

Translation of: Prolog

`prime2(N)` can be used to generate primes until memory is exhausted.

Difference from Prolog implementation: Picat does not support `between/3` with "inf" as upper bound, so a high number (here 2**156+1) must be used.

```prime2(2).
prime2(N) :-
between(3, 2**156+1, N),
N mod 2 = 1,              % odd
M is floor(sqrt(N+1)),    % round-off paranoia
Max is (M-1) // 2,        % integer division
foreach(I in 1..Max) N mod (2*I+1) > 0 end.```

Test

```go =>
println([I : I in 1..100, is_prime1(I)]),
nl,
foreach(P in 1..6)
Primes = [ I : I in 1..10**P, is_prime1(I)],
println([10**P,Primes.len])
end,
nl.```

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]

[10,4]
[100,25]
[1000,168]
[10000,1229]
[100000,9592]
[1000000,78498]```

Benchmark

Times for calculating the number of primes below 10, 100,1_000,10_000, 100_000, and 1_000_000 respectively.

• imperative: `is_prime1/1` (0.971)
• recursive: `is_prime2/1` (3.258s)
• functional: `is_prime3/1` (0.938s)
• test/generate `prime2/1` (2.129s)

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

PL/M

This can be compiled with the original 8080 PL/M compiler and run under CP/M or an emulator or clone.
Note that all integers in 8080 PL/M are unsigned.

```100H: /* TEST FOR PRIMALITY BY TRIAL DIVISION                                */

DECLARE FALSE LITERALLY '0', TRUE LITERALLY '0FFH';
/* CP/M BDOS SYSTEM CALL                                                  */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR\$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C );  END;
PR\$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S );  END;
PR\$NL:     PROCEDURE; CALL PR\$STRING( .( 0DH, 0AH, '\$' ) );       END;
PR\$NUMBER: PROCEDURE( N );
DECLARE V ADDRESS, N\$STR( 6 ) BYTE, W BYTE;
N\$STR( W := LAST( N\$STR ) ) = '\$';
N\$STR( W := W - 1 ) = '0' + ( ( V := N ) MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N\$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR\$STRING( .N\$STR( W ) );
END PR\$NUMBER;
/* INTEGER SUARE ROOT: BASED ON THE ONE IN THE PL/M FOR FROBENIUS NUMBERS */
DECLARE ( N, X0, X1 ) ADDRESS;
IF N <= 3 THEN DO;
IF N = 0 THEN X0 = 0; ELSE X0 = 1;
END;
ELSE DO;
X0 = SHR( N, 1 );
DO WHILE( ( X1 := SHR( X0 + ( N / X0 ), 1 ) ) < X0 );
X0 = X1;
END;
END;
RETURN X0;
END SQRT;

IS\$PRIME: PROCEDURE( N )BYTE; /* RETURNS TRUE IF N IS PRIME, FALSE IF NOT */
IF N < 2 THEN RETURN FALSE;
ELSE IF ( N AND 1 ) = 0 THEN RETURN N = 2;
ELSE DO;
/* ODD NUMBER > 2                                                   */
DO I = 3 TO SQRT( N ) BY 2;
IF N MOD I = 0 THEN RETURN FALSE;
END;
RETURN TRUE;
END;
END IS\$PRIME;

/* TEST THE IS\$PRIME PROCEDURE                                            */
DO I = 0 TO 100;
IF IS\$PRIME( I ) THEN DO;
CALL PR\$CHAR( ' ' );
CALL PR\$NUMBER( I );
END;
END;
CALL PR\$NL;

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

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 #True
EndProcedure
```

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

Quackery

`sqrt` is defined at Isqrt (integer square root) of X#Quackery.

```  [ dup 4 < iff [ 1 > ] done
dup 1 & not iff [ drop false ] done
true swap dup sqrt
0 = iff [ 2drop not ] done
1 >> times
[ dup i^ 1 << 3 + mod 0 = if
[ dip not conclude ] ]
drop ]                              is isprime ( n --> b )```

R

```is.prime <- function(n) n == 2 || n > 2 && n %% 2 == 1 && (n < 9 || all(n %% seq(3, floor(sqrt(n)), 2) > 0))

which(sapply(1:100, is.prime))
# [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```

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

Raku

(formerly 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 definition
sub prime(\$i) {
my \limit = \$i.sqrt.floor;
@isprime[\$i] //= so (\$i %% none @primes ...^ { \$_ > limit })
}

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

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*/
say
say  "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*/
say
say  "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*/
say
say  "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 }
end
end
p (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
end
end
p (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])
end
p 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
```

Prime Generators Tests

```Mathematicaly basis of Prime Generators
```
```require "benchmark/ips"

# the simplest PG primality test using the P3 prime generator
# reduces the number space for primes to 2/6 (33.33%) of all integers

def primep3?(n)                           # P3 Prime Generator primality test
# P3 = 6*k + {5, 7}                     # P3 primes candidates (pc) sequence
return n | 1 == 3 if n < 5              # n: 0,1,4|false, 2,3|true
return false if n.gcd(6) != 1           # 1/3 (2/6) of integers are P3 pc
p, sqrtn = 5, Integer.sqrt(n)           # first P3 sequence value
until p > sqrtn
return false if n % p == 0 || n % (p + 2) == 0  # if n is composite
p += 6      # first prime candidate for next kth residues group
end
true
end

# PG primality test using the P5 prime generator
# reduces the number space for primes to 8/30 (26.67%) of all integers

def primep5?(n)                           # P5 Prime Generator primality test
# P5 = 30*k + {7,11,13,17,19,23,29,31} # P5 primes candidates sequence
return [2, 3, 5].include?(n) if n < 7  # for small and negative values
return false if n.gcd(30) != 1         # 4/15 (8/30) of integers are P5 pc
p, sqrtn = 7, Integer.sqrt(n)          # first P5 sequence value
until p > sqrtn
return false if                      # if n is composite
n % (p)    == 0 || n % (p+4)  == 0 || n % (p+6)  == 0 || n % (p+10) == 0 ||
n % (p+12) == 0 || n % (p+16) == 0 || n % (p+22) == 0 || n % (p+24) == 0
p += 30  # first prime candidate for next kth residues group
end
true
end

# PG primality test using the P7 prime generator
# reduces the number space for primes to 48/210 (22.86%) of all integers

def primep7?(n)
# P7 = 210*k + {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,121,127,131,137,139,143,149,151,157,163,
#      167,169,173,179,181,187,191,193,197,199,209,211}
return [2, 3, 5, 7].include?(n) if n < 11
return false if n.gcd(210) != 1         # 8/35 (48/210) of integers are P7 pc
p, sqrtn = 11, Integer.sqrt(n)          # first P7 sequence value
until p > sqrtn
return false if
n % (p)     == 0 || n % (p+2)   == 0 || n % (p+6)   == 0 || n % (p+8)   == 0 ||
n % (p+12)  == 0 || n % (p+18)  == 0 || n % (p+20)  == 0 || n % (p+26)  == 0 ||
n % (p+30)  == 0 || n % (p+32)  == 0 || n % (p+36)  == 0 || n % (p+42)  == 0 ||
n % (p+48)  == 0 || n % (p+50)  == 0 || n % (p+56)  == 0 || n % (p+60)  == 0 ||
n % (p+62)  == 0 || n % (p+68)  == 0 || n % (p+72)  == 0 || n % (p+78)  == 0 ||
n % (p+86)  == 0 || n % (p+90)  == 0 || n % (p+92)  == 0 || n % (p+96)  == 0 ||
n % (p+98)  == 0 || n % (p+102) == 0 || n % (p+110) == 0 || n % (p+116) == 0 ||
n % (p+120) == 0 || n % (p+126) == 0 || n % (p+128) == 0 || n % (p+132) == 0 ||
n % (p+138) == 0 || n % (p+140) == 0 || n % (p+146) == 0 || n % (p+152) == 0 ||
n % (p+156) == 0 || n % (p+158) == 0 || n % (p+162) == 0 || n % (p+168) == 0 ||
n % (p+170) == 0 || n % (p+176) == 0 || n % (p+180) == 0 || n % (p+182) == 0 ||
n % (p+186) == 0 || n % (p+188) == 0 || n % (p+198) == 0 || n % (p+200) == 0
p += 210    # first prime candidate for next  kth residues group
end
true
end

# Benchmarks to test for various size primes

p = 541
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
b.compare!
puts
end

p = 1000003
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
b.compare!
puts
end

p = 4294967291            # largest prime < 2**32
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
b.compare!
puts
end

p = (10 ** 16) * 2 + 3
Benchmark.ips do |b|
print "\np = #{p}"
b.report("primep3?") { primep3?(p) }
b.report("primep5?") { primep5?(p) }
b.report("primep7?") { primep7?(p) }
b.compare!
puts
end
```
Output:
```p = 541
Warming up --------------------------------------
primep3?   109.893k i/100ms
primep5?   123.949k i/100ms
primep7?    44.216k i/100ms
Calculating -------------------------------------
primep3?      1.598M (± 3.4%) i/s -      8.022M in   5.025036s
primep5?      1.872M (± 6.3%) i/s -      9.420M in   5.059896s
primep7?    502.040k (± 1.2%) i/s -      2.520M in   5.020919s

Comparison:
primep5?:  1871959.0 i/s
primep3?:  1598489.8 i/s - 1.17x  slower
primep7?:   502039.8 i/s - 3.73x  slower

p = 1000003
Warming up --------------------------------------
primep3?     5.850k i/100ms
primep5?     9.013k i/100ms
primep7?    10.889k i/100ms
Calculating -------------------------------------
primep3?     59.965k (± 1.1%) i/s -    304.200k in   5.073641s
primep5?     92.561k (± 2.1%) i/s -    468.676k in   5.065709s
primep7?    109.335k (± 0.8%) i/s -    555.339k in   5.079549s

Comparison:
primep7?:   109334.7 i/s
primep5?:    92561.4 i/s - 1.18x  slower
primep3?:    59964.5 i/s - 1.82x  slower

p = 4294967291
Warming up --------------------------------------
primep3?    92.000  i/100ms
primep5?   148.000  i/100ms
primep7?   184.000  i/100ms
Calculating -------------------------------------
primep3?    926.647  (± 1.1%) i/s -      4.692k in   5.064067s
primep5?      1.480k (± 1.7%) i/s -      7.400k in   5.001399s
primep7?      1.804k (± 1.0%) i/s -      9.200k in   5.099110s

Comparison:
primep7?:     1804.4 i/s
primep5?:     1480.0 i/s - 1.22x  slower
primep3?:      926.6 i/s - 1.95x  slower

p = 20000000000000003
Warming up --------------------------------------
primep3?     1.000  i/100ms
primep5?     1.000  i/100ms
primep7?     1.000  i/100ms
Calculating -------------------------------------
primep3?      0.422  (± 0.0%) i/s -      3.000  in   7.115929s
primep5?      0.671  (± 0.0%) i/s -      4.000  in   5.957077s
primep7?      0.832  (± 0.0%) i/s -      5.000  in   6.007834s

Comparison:
primep7?:        0.8 i/s
primep5?:        0.7 i/s - 1.24x  slower
primep3?:        0.4 i/s - 1.97x  slower
```

Run BASIC

```' Test and display primes 1 .. 50
for 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 = 1
for 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).filter(|i| is_prime(*i)) {
println!("{} ", i);
}
}
```
Output:
`2 3 5 7 11 13 17 19 23 29 `

S-BASIC

```\$lines

\$constant FALSE = 0
\$constant TRUE = 0FFFFH

rem - return p mod q
function mod(p, q = integer) = integer
end = p - q * (p / q)

rem - return true (-1) if n is prime, otherwise false (0)
function isprime(n = integer) = integer
var i, limit, result = integer
if n = 2 then
result = TRUE
else if (n < 2) or (mod(n,2) = 0) then
result = FALSE
else
begin
limit = int(sqr(n))
i = 3
while (i <= limit) and (mod(n, i) <> 0) do
i = i + 2
result = not (i <= limit)
end
end = result

rem - test by looking for primes in range 1 to 50
var i = integer
for i = 1 to 50
if isprime(i) then print using "#####";i;
next i

end```
Output:
```     2    3    5    7   11   13   17   19   23   29   31   37   41   43   47
```

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;
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.tailrec
import 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 = 1
isp1    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 .. 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
```

SQL

Works with: T-SQL
```declare @number int
set @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 primalityTest
option (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}
}
}
}
```

A version that works with Swift 5.x and probably later. Does not need to import Foundation

```extension Int
{
func isPrime() -> Bool
{
if self < 3
{
return self == 2
}
else
{
let upperLimit = Int(Double(self).squareRoot())
return !self.isMultiple(of: 2) && !stride(from: 3, through: upperLimit, by: 2)
.contains(where: { factor in self.isMultiple(of: factor) })
}
}
}
```

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

Tiny BASIC

```    PRINT "ENTER A NUMBER "
INPUT P
GOSUB 100
IF Z = 1 THEN PRINT "It is prime."
IF Z = 0 THEN PRINT "It isn't prime."
END

100 REM PRIMALITY OF THE NUMBER P BY TRIAL DIVISION
IF P < 2 THEN RETURN
LET Z = 1
IF P < 4 THEN RETURN
LET I = 2
110 IF (P/I)*I = P THEN LET Z = 0
IF Z = 0 THEN RETURN
LET I = I + 1
IF I*I <= P THEN GOTO 110
RETURN```

uBasic/4tH

```10 LET n=0: LET p=0
20 INPUT "Enter number: ";n
30 LET p=0 : IF n>1 THEN GOSUB 1000
40 IF p=0 THEN PRINT n;" is not prime!"
50 IF p#0 THEN PRINT n;" is prime!"
60 GOTO 10
1000 REM ***************
1001 REM * PRIME CHECK *
1002 REM ***************
1010 LET p=0
1020 IF (n%2)=0 THEN RETURN
1030 LET p=1 : PUSH n,0 : GOSUB 9030
1040 FOR i=3 TO POP() STEP 2
1050 IF (n%i)=0 THEN LET p=0: PUSH n,0 : GOSUB 9030 : LET i=POP()
1060 NEXT i
1070 RETURN
9030 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/~& iota@K31```

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 If
End 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 If
End Function

For n = 1 To 50
If IsPrime(n) Then
WScript.StdOut.Write n & " "
End If
Next
```
Output:
```2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
```

Wren

Library: Wren-fmt
```import "/fmt" for Fmt

var isPrime = Fn.new { |n|
if (n < 2) return false
if (n%2 == 0) return n == 2
var p = 3
while (p * p <= n) {
if (n%p == 0) return false
p = p + 2
}
return true
}

var tests = [2, 5, 12, 19, 57, 61, 97]
System.print("Are the following prime?")
for (test in tests) {
System.print("%(Fmt.d(2, test)) -> %(isPrime.call(test) ? "yes" : "no")")
}
```
Output:
```Are the following prime?
2 -> yes
5 -> yes
12 -> no
19 -> yes
57 -> no
61 -> yes
97 -> yes
```

XPL0

```func Prime(N);          \Return 'true' if N is a prime number
int  N;
int  I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true;
];

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

Yabasic

Translation of: FreeBASIC
```for i = 1 to 99
if isPrime(i)  print str\$(i), " ";
next i
print
end

sub isPrime(v)
if v < 2  return False
if mod(v, 2) = 0  return v = 2
if mod(v, 3) = 0  return v = 3
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub```

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