Primality by trial division: Difference between revisions

 

=={{header|11l}}==

I n < 2

R 0B

I n % i == 0

R 0B

 

=={{header|360 Assembly}}==

PRIMEDIV CSECT

USING PRIMEDIV,R13 base register

XDEC DS CL12 temp for xdeco

YREGS

{{out}}

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

=={{header|68000 Assembly}}==

; REG USAGE:

; D0 = input (unsigned 32-bit integer)

MOVEM.L (SP)+,D1-D4 ;pop D1-D4

RTS

 

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program testPrime64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

 

=={{header|ABAP}}==

public

create public .

RETURN.

endmethod.

 

=={{header|ACL2}}==

(declare (xargs :measure (nfix (- x i))))

(if (zp (- (- x i) 1))

(defun is-prime (x)

(or (= x 2)

 

=={{header|Action!}}==

CARD i

 

Test(120)

Test(0)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Primality_by_trial_division.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

if(n < 2) return false;

if(n % i == 0) return false;

return true;

 

=={{header|Ada}}==

Test : Natural;

begin

end if;

return True;

 

<code>Sqrt</code> is made visible by a with / use clause on <code>Ada.Numerics.Elementary_Functions</code>.

 

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

(Item /= 1 and then

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

 

procedure Test_Prime is

raise Program_Error with "Test_Prime failed!";

end if;

 

=={{header|ALGOL 68}}==

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}}

{{prelude/is_prime.a68}};

INT upb=100;

printf(($" The primes up to "g(-3)" are:"l$,upb));

OD;

printf($l$)

{{out}}

The primes up to 100 are:

 

=={{header|ALGOL-M}}==

BEGIN

 

 

END

{{out}}

<pre>

 

=={{header|ALGOL W}}==

% uses trial division %

logical procedure isPrime ( integer value n ) ;

end;

havePrime

Test program:

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 )

{{out}}

2 3 5 7 11 13 17 19 23 29 31

=={{header|AppleScript}}==

 

if (n < 3) then return (n is 2)

if (n mod 2 is 0) then return false

if (isPrime(n)) then set end of output to n

end repeat

 

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

 

if (n < 4) then return (n > 1)

if ((n mod 2 is 0) or (n mod 3 is 0)) then return false

if (isPrime(n)) then set end of output to n

end repeat

 

{{output}}

 

=={{header|Arturo}}==

if n=2 -> return true

if n=3 -> return true

loop 1..20 'i [

print ["isPrime?" i "=" isPrime? i ]

 

{{out}}

=={{header|AutoHotkey}}==

[http://www.autohotkey.com/forum/topic44657.html Discussion]

Loop

MsgBox % A_Index-3 . " is " . (IsPrime(A_Index-3) ? "" : "not ") . "prime."

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

 

=={{header|AutoIt}}==

 

AutoIt Version: 3.3.8.1

Return True

EndFunc

 

=={{header|AWK}}==

Or more legibly, and with n <= 1 handling

 

if (n <= 1) return 0

for (d = 2; d <= sqrt(n); d++)

}

 

 

=={{header|B}}==

{{trans|C}}

{{works with|B as on PDP7/UNIX0|(proto-B?)}}

auto p;

if(n<2) return(0);

}

return(1);

 

=={{header|BASIC}}==

{{works with|QuickBasic|4.5}}

Returns 1 for prime, 0 for non-prime

STATIC i AS INTEGER

IF n = 2 THEN

FOR n = 1 TO 50

IF prime(n) = 1 THEN PRINT n;

{{out}}

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

 

==={{header|IS-BASIC}}===

110 FOR X=0 TO 100

120 IF PRIME(X) THEN PRINT X;

230 NEXT

240 END IF

 

==={{header|True BASIC}}===

{{trans|BASIC}}

IF n = 2 THEN

LET isPrime = 1

IF isPrime(n) = 1 THEN PRINT n;

NEXT n

 

==={{header|ZX Spectrum Basic}}===

20 INPUT "Enter number: ";n

30 IF n>1 THEN GO SUB 1000

1060 NEXT i

1070 RETURN

{{out}}

<pre>

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

if isPrime(i) then print string(i); " ";

next i

end while

return True

 

=={{header|BBC BASIC}}==

IF FNisprime(i%) PRINT ; i% " is prime"

NEXT

IF n% MOD t% = 0 THEN = FALSE

NEXT

{{out}}

<pre>2 is prime

 

=={{header|bc}}==

define p(n) {

auto i

}

return(1)

 

=={{header|BCPL}}==

 

let sqrt(s) =

if isprime(i) then writef("%N ",i)

wrch('*N')

{{out}}

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

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 (1023²), thus a maximum testable prime of 1,046,527.

 

v_v#`\*:%*:*84\/*:*84::+<

v >::48*:*/\48*:*%%!#v_1^

 

{{out}} (multiple runs)

 

=={{header|Bracmat}}==

= incs n I inc

. 4 2 4 2 4 6 2 6:?incs

)

)

{{out}}

<pre>100000000003

 

=={{header|Brainf***}}==

+]++++[->++++++++<]>.<+++++++[->++++++++++<]>+++.++++++++++.<+++++++++[->-------

--<]>--.[-]<<<->[->+>+<<]>>-[+<[[->>+>>+<<<<]>>[-<<+>>]<]>>[->-[>+>>]>[+[-<+>]>>

>]<<<<<]>[-]>[>+>]<<[-]+[-<+]->>>--]<[->+>+<<]>>>>>>>[-<<<<<->>>>>]<<<<<--[>++++

++++++[->+++++++++++<]>.+.+++++.>++++[->++++++++<]>.>]++++++++++[->+++++++++++<]

Explanation:

->,[.>,]>-<++++++[-<+[---------<+]->+[->+]-<]>+<-<+[-<+]>>+[-<[->++++++++++<]>>+]< takes input

>++++[->++++++++<]>.<+++++++[->++++++++++<]>+++.++++++++++.<+++++++++[->---------<]>--.[-]<< " is "

<[->+>+<<]>>>>>>>[-<<<<<->>>>>]<<<<<--

[>++++++++++[->+++++++++++<]>.+.+++++.>++++[->++++++++<]>.>] "not "

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

 

=={{header|Burlesque}}==

 

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

Version not using the ''fc'' function:

 

1

blsq ) 12^^2\/?dr@.%{0==}ayn!

0

blsq ) 13^^2\/?dr@.%{0==}ayn!

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.

 

=={{header|C}}==

{

unsigned int p;

if (!(n % p)) return 0;

return 1;

 

=={{header|C sharp|C#}}==

{

if (n <= 1) return false;

if (n % i == 0) return false;

return true;

 

=={{header|C++}}==

 

bool is_prime(unsigned int n)

return false;

return true;

 

=={{header|Chapel}}==

{{trans|C++}}

{

if n == 2 then

return false;

return true;

 

=={{header|Clojure}}==

The function used in both versions:

 

Testing divisors are in range from '''3''' to '''&radic;{{overline|&nbsp;n&nbsp;}} &nbsp;''' with step '''2''':

(or (= 2 x)

(and (< 1 x)

(not-any? (partial divides? x)

(range 3 (inc (Math/sqrt x)) 2)))))

 

Testing only prime divisors:

 

(def primes (filter prime? (range)))

(not-any? (partial divides? x)

(take-while (partial >= (Math/sqrt x)) primes))))

 

=={{header|CLU}}==

x0: int := s/2

if x0=0 then return(s) end

end

end

{{out}}

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

 

=={{header|CMake}}==

function(primep var n)

if(n GREATER 2)

set(${var} false PARENT_SCOPE) # n < 2 is not prime.

endif()

 

foreach(i -5 1 2 3 37 39)

primep(b ${i})

message(STATUS "${i} is _not_ prime.")

endif(b)

 

=={{header|COBOL}}==

Program-Id. Primality-By-Subdiv.

 

 

Goback

 

=={{header|CoffeeScript}}==

# simple prime detection using trial division, works

# for all integers

for i in [-1..100]

 

=={{header|Common Lisp}}==

"Is N prime?"

(and (> n 1)

(or (= n 2) (oddp n))

(loop for i from 3 to (isqrt n) by 2

===Alternate solution===

I use [https://franz.com/downloads/clp/survey Allegro CL 10.1]

 

 

(defun prime(n)

(format t "~d is not a prime number" n)))

(prime 7)

Output:

7 is a prime number

https://www.academia.edu/19786419/PRIMES-UTILS_HANDBOOK

https://www.academia.edu/42734410/Improved_Primality_Testing_and_Factorization_in_Ruby_revised

require "benchmark"

 

b.report("primep7?") { primep7?(p) }

puts

{{out}}

<pre>p = 541

=={{header|D}}==

===Simple Version===

 

bool isPrime1(in int n) pure nothrow {

void main() {

iota(2, 40).filter!isPrime1.writeln;

{{out}}

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

===Version with excluded multiplies of 2 and 3===

Same output.

// Adapted from: http://www.devx.com/vb2themax/Tip/19051

// Test 1, 2, 3 and multiples of 2 and 3:

 

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.

 

bool isPrime3(T)(in T n) pure nothrow {

void main() {

iota(2, 40).filter!isPrime3.writeln;

 

=={{header|Delphi}}==

=== First ===

var

I: Integer;

Break;

end;

 

=== Second ===

var

i: integer;

until i > Sqrt(x);

Result := True;

 

=={{header|E}}==

{{trans|D}}

if (n == 2) {

return true

return true

}

 

=={{header|EchoLisp}}==

 

;; Try divisors iff n = 2k + 1

(filter is-prime? (range 1 100))

 

=={{header|Eiffel}}==

APPLICATION

 

end

 

<pre>False

True

=={{header|Elixir}}==

{{trans|Erlang}}

def is_prime(2), do: true

def is_prime(n) when n<2 or rem(n,2)==0, do: false

end

 

{{out}}

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

=={{header|Emacs Lisp}}==

{{libheader|cl-lib}}

(not (or (< a 2)

(cl-loop for x from 2 to (sqrt a)

when (zerop (% a x))

 

More concise, a little bit faster:

(and (> a 1)

(cl-loop for x from 2 to (sqrt a)

 

A little bit faster:

(and (> a 1)

(or (= a 2) (cl-oddp a))

(cl-loop for x from 3 to (sqrt a) by 2

 

More than 2 times faster, than the previous, doesn't use <tt>loop</tt> macro:

(not (or (< a 2)

 

Almost 2 times faster, than the previous:

(not (or (< a 2)

(and (/= a 2) (cl-evenp a))

 

=={{header|Erlang}}==

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;

 

=={{header|ERRE}}==

 

PROCEDURE ISPRIME(N%->OK%)

END FOR

 

{{out}}

2 is prime

 

=={{header|Euphoria}}==

if n<=2 or remainder(n,2)=0 then

return 0

return 1

end if

 

=={{header|F Sharp|F#}}==

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 277 is prime`` () =

{{out}}

> isPrime 1111111111111111111UL;;

 

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

let rec test n =

if n * n > x then true else

 

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.

and IsPrime number =

false

else

 

=={{header|Factor}}==

 

: prime? ( n -- ? )

{ [ dup even? ] [ 2 = ] }

[ 3 over sqrt 2 <range> [ mod 0 > ] with all? ]

 

=={{header|FALSE}}==

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

 

=={{header|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.

 

FUNCTION ISPRIME(n AS INTEGER) AS INTEGER

NEXT

 

{{out}}

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

=={{header|Forth}}==

 

dup 2 < if drop false

else dup 2 = if drop true

then 2 +

repeat 2drop true

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

LOGICAL :: isPrime

INTEGER, INTENT(IN) :: number

END DO

END IF

 

=={{header|FreeBASIC}}==

 

Function isPrime(n As Integer) As Boolean

Print : Print

Print "Press any key to quit"

 

{{out}}

=={{header|Frink}}==

It is unnecessary to write this function because Frink has an efficient <CODE>isPrime[x]</CODE> 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 <CODE>sqrt[x]</CODE> but because of floating-point error the square root is slightly smaller than the true square root!

{

for p = primes[]

return true

 

 

=={{header|FunL}}==

 

def

| otherwise = (3..int(sqrt(n)) by 2).forall( (/|n) )

 

{{out}}

10000000019

 

=={{header|FutureBasic}}==

 

local fn isPrime( n as long ) as Boolean

next

 

Output:

Prime numbers between 0 and 1000:

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=85fbc7936b17b3009af282752aa29df7 Click this link to run this code]'''

 

Public Sub Main()

Return bReturn

 

Output:

<pre>1 is prime

 

=={{header|GAP}}==

local k, m;

if n < 5 then

 

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

 

=={{header|Go}}==

if n < 0 { n = -n }

switch {

}

return true

 

Or, using recursion:

 

if n < 0 { n = -n }

if n <= 2 {

}

return true

 

=={{header|Groovy}}==

it == 2 ||

it > 1 &&

}

 

{{out}}

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

=={{header|Haskell}}==

(used [[Emirp_primes#List-based|here]] and [[Sequence_of_primes_by_Trial_Division#Haskell|here]]). The basic divisibility test by odd numbers:

 

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:

 

-- primeNums = filter (noDivsBy [2..]) [2..]

primeNums = 2 : 3 : filter (noDivsBy $ tail primeNums) [5,7..]

 

Any increasing ''unbounded'' sequence of numbers that includes all primes (above the first few, perhaps) could be used with the testing function <code>noDivsBy</code> to define the <code>isPrime</code> function -- but using just primes is better, produced e.g. by [[Sieve of Eratosthenes#Haskell|Sieve of Eratosthenes]], or <code>noDivsBy</code> itself can be used to define <code>primeNums</code> 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:

 

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

 

=={{header|HicEst}}==

Euler = n^2 + n + 41

IF( Prime(Euler) == 0 ) WRITE(Messagebox) Euler, ' is NOT prime for n =', n

Prime = 1

ENDIF

 

=={{header|Icon}} and {{header|Unicon}}==

Procedure shown without a main program.

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

 

=={{header|J}}==

{{eff note|J|1&p:}}

 

=={{header|Java}}==

if(a == 2){

return true;

}

return true;

===By Regular Expression===

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

 

=={{header|JavaScript}}==

if (n == 2 || n == 3 || n == 5 || n == 7) {

return true;

return true;

}

 

=={{header|Joy}}==

=={{header|Julia}}==

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

1 < n || return false

n != 2 || return true

else

println("The function does not accurately calculate primes.")

{{out}}

The primes <= 100 are:

 

=={{header|K}}==

&isprime'!100

 

=={{header|Kotlin}}==

fun isPrime(n: Int): Boolean {

if (n < 2) return false

// test by printing all primes below 100 say

(2..99).filter { isPrime(it) }.forEach { print("$it ") }

{{out}}

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

{{trans|Go}}

{{works with|langur|0.8.2}}

val .n = abs(.i)

if .n <= 2: return .n == 2

}

 

 

=== Functional ===

 

{{works with|langur|0.8.1}}

.i > 2 and not any f(.x) .i div .x, pseries 2 to .i ^/ 2

 

 

{{out}}

 

=={{header|Liberty BASIC}}==

print

[start]

next i

isPrime=1

{{out}}

<pre>Rosetta Code - Primality by trial division

 

=={{header|Lingo}}==

if n<=1 or (n>2 and n mod 2=0) then return FALSE

sq = sqrt(n)

end repeat

return TRUE

repeat with i = 0 to 100

if isPrime(i) then primes.add(i)

end repeat

{{out}}

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

 

=={{header|Logo}}==

if :n < 2 [output "false]

if :n = 2 [output "true]

for [i 3 [sqrt :n] 2] [if equal? 0 modulo :n :i [output "false]]

output "true

 

=={{header|LSE64}}==

2dup : over over

even? : 1 & 0 =

prime? : dup even? then drop false

prime? : dup 2 = then drop true

 

=={{header|Lua}}==

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

return false

 

return true

Type of number Decimal.

 

=={{header|M2000 Interpreter}}==

Inventory Known1=2@, 3@

IsPrime=lambda Known1 (x as decimal) -> {

Print

Print "Found ";count;" primes"

 

=={{header|M4}}==

`ifelse(eval($2*$2>$1),1,

1,

 

isprime(9)

{{out}}

0

=={{header|Maple}}==

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

if n <= 1 then

false

true

end if

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

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

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

 

=={{header|MATLAB}}==

 

if n == 2

isPrime = all(mod(n, (3:round(sqrt(n))) ));

{{out|Sample output}}

 

ans =

 

 

=={{header|Maxima}}==

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

 

=={{header|min}}==

{{works with|min|0.19.3}}

:n 3 :i n sqrt :m true :p

(i m <=) (

((true) (_prime?))

) case

 

=={{header|МК-61/52}}==

ИП0 2 / {x} x#0 34

3 П4 ИП0 ИП4 / {x} x#0 34 КИП4 КИП4

 

=={{header|MUMPS}}==

QUIT:(N=2) 1

NEW I,R

IF R FOR I=3:2:(N**.5) SET R=N#I Q:'R

KILL I

Usage (0 is false, nonzero is true):

<pre>USER>W $$ISPRIME^ROSETTA(2)

 

=={{header|NetRexx}}==

 

options replace format comments java crossref savelog symbols nobinary

 

method isFalse public static returns boolean

{{out}}

<pre>$ java -cp . RCPrimality

===[[#REXX|Rexx]] version reimplemented in [[NetRexx]]===

{{trans|REXX}}

 

options replace format comments java crossref savelog symbols nobinary

end

 

 

=={{header|newLISP}}==

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

 

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

 

(println (filter is-prime? (sequence 1 100)))

 

{{Output}}

=={{header|Nim}}==

Here are three ways to test primality using trial division.

 

proc prime(a: int): bool =

 

for i in 2..30:

 

{{out}}

 

=={{header|Objeck}}==

if(n <= 1) {

return false;

return true;

 

=={{header|OCaml}}==

if n = 2 then true

else if n < 2 || n mod 2 = 0 then false

else if n mod k = 0 then false

else loop (k+2)

 

=={{header|Octave}}==

This function works on vectors and matrix.

for r = 1:rows(n)

for c = 1:columns(n)

p = [1:100];

pv = isthisprime(p);

 

=={{header|Oforth}}==

| i |

self 1 <= ifTrue: [ false return ]

self isEven ifTrue: [ false return ]

3 self sqrt asInteger for: i [ self i mod ifzero: [ false return ] ]

{{out}}

<pre>#isPrime 1000 seq filter println

 

=={{header|Ol}}==

(define (prime? number)

(define max (sqrt number))

(> (modulo number 2) 0)

(loop 3))))

Testing:

; first prime numbers less than 100

(for-each (lambda (n)

12345676543211234567654321123456765432112345676543211234567654321123456765432112345676543211234567654321

))

{{out}}

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

 

=={{header|Oz}}==

local IPrime in

fun {IPrime N Acc}

else {IPrime N 2} end

end

 

=={{header|Panda}}==

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

p.gt(1) where q=p.sqrt NO(p.mod(2..q)==0)

 

 

=={{header|PARI/GP}}==

if(n < 4, return(n > 1)); /* Handle negatives */

forprime(p=2,sqrtint(n),

);

1

 

=={{header|Pascal}}==

{{trans|BASIC}}

 

function prime(n: integer): boolean;

if (prime(n)) then

write(n, ' ');

{{out}}

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

===improved using number wheel===

{{libheader|primTrial}}{{works with|Free Pascal}}

{$IFDEF FPC}

{$MODE DELPHI}{$Smartlink ON}

write(actPrime,' ');

until nextPrime > 50;

;Output:

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

=={{header|Perl}}==

A simple idiomatic solution:

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

$n > 1

}

 

 

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

my $n = shift;

return ($n >= 2) if $n < 4;

my $s = 0;

$s += !!isprime($_) for 1..100000;

===By Regular Expression===

 

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

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

}

 

=={{header|Phix}}==

<span style="color: #008080;">function</span> <span style="color: #000000;">is_prime_by_trial_division</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">32</span><span style="color: #0000FF;">),</span><span style="color: #000000;">is_prime_by_trial_division</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

 

=={{header|PHP}}==

function prime($a) {

if (($a % 2 == 0 && $a != 2) || $a < 2)

if (prime($x)) echo "$x\n";

 

===By Regular Expression===

function prime($a) {

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

}

 

=={{header|Picat}}==

Here are four different versions.

===Iterative===

if N == 2 then

true

N mod I > 0

end

 

===Recursive===

(N == 2 ; is_prime2b(N,3)).

 

;

is_prime2b(N,Div+2)

 

===Functional===

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.

 

===Generator approach===

Difference from Prolog implementation: Picat does not support <code>between/3</code> with

"inf" as upper bound, so a high number (here 2**156+1) must be used.

prime2(N) :-

between(3, 2**156+1, N),

M is floor(sqrt(N+1)), % round-off paranoia

Max is (M-1) // 2, % integer division

 

===Test===

println([I : I in 1..100, is_prime1(I)]),

nl,

println([10**P,Primes.len])

end,

 

 

 

=={{header|PicoLisp}}==

(or

(= N 2)

(for (D 3 T (+ D 2))

(T (> D S) T)

 

=={{header|PL/I}}==

declare n fixed (15);

declare i fixed (10);

end;

return ('1'b);

 

=={{header|PL/M}}==

This can be compiled with the original 8080 PL/M compiler and run under CP/M or an emulator or clone.

<br>Note that all integers in 8080 PL/M are unsigned.

 

DECLARE FALSE LITERALLY '0', TRUE LITERALLY '0FFH';

CALL PR$NL;

 

{{out}}

<pre>

 

=={{header|PowerShell}}==

function isPrime ($n) {

if ($n -eq 1) {$false}

}

}

<b>Output:</b>

<pre>isPrime 1 : False

=={{header|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(N) :-

between(3, inf, N),

M is floor(sqrt(N+1)), % round-off paranoia

Max is (M-1) // 2, % integer division

Example using SWI-Prolog:

<pre>?- time( (bagof( P, (prime(P), ((P > 100000, !, fail); true)), Bag),

 

=={{header|PureBasic}}==

Protected k

 

 

ProcedureReturn #True

 

=={{header|Python}}==

The simplest primality test, using trial division:

{{works with|Python|2.5}}

Another test. Exclude even numbers first:

if a == 2: return True

if a < 2 or a % 2 == 0: return False

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

{{works with|Python|2.4}}

if a < 2: return False

if a == 2 or a == 3: return True # manually test 2 and 3

i = 6 - i # this modifies 2 into 4 and viceversa

 

===By Regular Expression===

Regular expression by "Abigail".<br>

(An explanation is given in "[http://paddy3118.blogspot.com/2009/08/story-of-regexp-and-primes.html The Story of the Regexp and the Primes]").

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

 

=={{header|Qi}}==

K N -> true where (> (* K K) N)

K N -> false where (= 0 (MOD N K))

2 -> true

N -> false where (= 0 (MOD N 2))

 

=={{header|Quackery}}==

<code>sqrt</code> is defined at [[Isqrt (integer square root) of X#Quackery]].

 

dup 1 & not iff [ drop false ] done

true swap dup sqrt

[ dip not conclude ] ]

drop ] is isprime ( n --> b )

 

=={{header|R}}==

 

which(sapply(1:100, is.prime))

 

=={{header|Racket}}==

 

(define (prime? number)

((even? number) (= 2 number))

(else (for/and ((i (in-range 3 (ceiling (sqrt number)))))

 

=={{header|Raku}}==

(formerly Perl 6)

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

$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 <tt>//=</tt> 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 @isprime = False,False; # 0 and 1 are not prime by definition

sub prime($i) {

}

 

 

=={{header|REBOL}}==

case [

n = 2 [ true ]

]

]

 

 

=={{header|REXX}}==

<br>function slowed up the function &nbsp; (for all three REXX versions), &nbsp; however, for larger numbers of &nbsp; '''N''', &nbsp; it would

<br>be faster.

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. */

end /*k*/ /*divide up through the √ x */

/*Note: // is ÷ remainder.*/

{{out|output|text=&nbsp; when using the default input of: &nbsp; <tt> 100 </tt>}}

<pre>

This version separates multiple-clause &nbsp; '''if''' &nbsp; statements, and also tests for low primes,

<br>making it about 8% faster.

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. */

if x//(k+2)==0 then return 0 /* ··· and the next umpty one. */

end /*k*/ /*Note: REXX // is ÷ remainder.*/

{{out|output|text=&nbsp; is identical to the first version when the same input is used.}}

 

<br>also an optimized version of the testing of low primes is used, making it about 22% faster.

<br><br>Note that the &nbsp; '''do ... until ...''' &nbsp; was changed to &nbsp; '''do ... while ...'''.

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. */

if x//(k+2)==0 then return 0 /* ··· and the next also. ___ */

end /*k*/ /*divide up through the √ x */

{{out|output|text=&nbsp; is identical to the first version when the same input is used.}}<br><br>

 

=={{header|Ring}}==

flag = isPrime(n)

if flag = 1 see n + " is a prime number"

if (num % i = 0) return 0 ok

next

 

=={{header|Ruby}}==

if a == 2

true

end

end

 

The '''prime''' package in the stdlib for Ruby contains this compact <code>Prime#prime?</code> method:

def prime?(value, generator = Prime::Generator23.new)

return false if value < 2

end

end

 

Without any fancy stuff:

(enclose = lambda { |primes|

primes.last.succ.upto(limit) do |trial_pri|

}).call([2])

end

 

{{out}}

 

===By Regular Expression===

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

 

===Prime Generators Tests===

https://www.academia.edu/19786419/PRIMES-UTILS_HANDBOOK

https://www.academia.edu/42734410/Improved_Primality_Testing_and_Factorization_in_Ruby_revised

 

# the simplest PG primality test using the P3 prime generator

b.compare!

puts

{{out}}

<pre>p = 541

 

=={{header|Run BASIC}}==

for i = 1 TO 50

if prime(i) <> 0 then print i;" ";

next i

[exit]

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

 

=={{header|Rust}}==

match n {

0 | 1 => false,

println!("{} ", i);

}

{{out}}

<pre>2 3 5 7 11 13 17 19 23 29 </pre>

 

=={{header|S-BASIC}}==

$lines

 

 

end

{{out}}

<pre>

 

=={{header|S-lang}}==

{

if (n == 2) return(1);

print(strjoin(list_to_array(lst), ", "));

}

{{out}}

"2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61"

 

=={{header|SAS}}==

do n=1 to 1000;

link primep;

return;

keep n;

 

=={{header|Scala}}==

===Simple version===

===Accelerated version [[functional_programming|FP]] and parallel runabled===

// {{Out}}Best seen running in your browser [https://scastie.scala-lang.org/1RLimJrRQUqkXWkUwUxgYg Scastie (remote JVM)].

def isPrime(n: Long) =

n > 1 && ((n & 1) != 0 || n == 2) && (n % 3 != 0 || n == 3) &&

println("All done")

 

===Accelerated version [[functional_programming|FP]], tail recursion===

Tests 1.3 M numbers against OEIS prime numbers.

import scala.io.Source

 

for (i <- 0 to 1299709) assert(isPrime(i) == oeisPrimes.contains(i.toString), s"Wrong $i")

 

 

=={{header|Scheme}}==

{{Works with|Scheme|R<math>^5</math>RS}}

(define (*prime? divisor)

(or (> (* divisor divisor) number)

(*prime? (+ divisor 1)))))

(and (> number 1)

 

(define (prime? n)

(if (< n 4) (> n 1)

(or (> (* k k) n)

(and (positive? (remainder n k))

 

=={{header|Seed7}}==

result

var boolean: prime is FALSE;

prime := testNum > upTo;

end if;

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

 

=={{header|Sidef}}==

given (a) {

when (2) { true }

default { 3 .. a.isqrt -> any { .divides(a) } -> not }

}

{{trans|Perl}}

Alternative version, excluding multiples of 2 and 3:

return (n >= 2) if (n < 4)

return false if (n%%2 || n%%3)

}

return true

 

=={{header|Smalltalk}}==

isPrime := [:n |

n even ifTrue: [ ^n=2 ]

^true

]

 

=={{header|SNOBOL4}}==

isprime isprime = n

le(n,1) :s(freturn)

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

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

===By Patterns===

Using the Abigail regex transated to Snobol patterns.

rprime str = dupl('1',n); rprime = n

pat1 = ('1' | '')

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

output = rprimes

{{out}}

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

=={{header|SQL}}==

{{works with|T-SQL}}

set @number = 514229 -- number to check

 

' is prime'

end primalityTest

 

=={{header|Standard ML}}==

if n = 2 then true

else if n < 2 orelse n mod 2 = 0 then false

else loop (k+2)

in loop 3

 

=={{header|Swift}}==

 

extension Int {

}

}

 

=={{header|Tcl}}==

if {$n <= 1} {return false}

if {$n == 2} {return true}

}

return true

 

=={{header|TI-83 BASIC}}==

 

=={{header|Tiny BASIC}}==

INPUT P

GOSUB 100

LET I = I + 1

IF I*I <= P THEN GOTO 110

 

=={{header|uBasic/4tH}}==

20 INPUT "Enter number: ";n

30 LET p=0 : IF n>1 THEN GOSUB 1000

If Abs(@(255)-Tos())<2 Then @(255)=Pop() : If Pop() Then Push @(255) : Return

@(255) = Pop() : Goto 9040

 

=={{header|UNIX Shell}}==

{{works with|pdksh}}

{{works with|zsh}}

typeset n=$1 p=3

(( n == 2 )) && return 0 # 2 is prime.

done

return 0 # Yes, n is prime.

{{works with|Bourne Shell}}

set -- "$1" 3

test "$1" -eq 2 && return 0 # 2 is prime.

done

return 0 # Yes, n is prime.

 

=={{header|Ursala}}==

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

#import nat

 

Test program to try it on a few numbers:

 

{{out}}

<true,false,true>

=={{header|V}}==

{{trans|Joy}}

2

[[dup * >] [true] [false] ifte [% 0 >] dip and]

[succ]

while

{{out|Using it}}

=true

|4 prime?

 

=={{header|VBA}}==

 

Sub FirstTwentyPrimes()

IsPrime = True

End If

{{out}}

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

=={{header|VBScript}}==

{{trans|BASIC}}

If n = 2 Then

IsPrime = True

WScript.StdOut.Write n & " "

End If

{{out}}

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

=={{header|Wren}}==

{{libheader|Wren-fmt}}

 

var isPrime = Fn.new { |n|

for (test in tests) {

System.print("%(Fmt.d(2, test)) -> %(isPrime.call(test) ? "yes" : "no")")

 

{{out}}

 

=={{header|XPL0}}==

int N;

int I;

Text(0, if Prime(Num) then "is " else "not ");

Text(0, "prime^M^J");

{{out}}

<pre>777777777

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

if isPrime(i) print str$(i), " ";

next i

wend

return True

 

=={{header|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

if(n.isEven or n<2) return(n==2);

(not [3..n.toFloat().sqrt().toInt(),2].filter1('wrap(m){n%m==0}))

{{out}}

<pre>zkl: [1..].filter(20,isPrime)