Primality by trial division: Difference between revisions

Use trial division.

 

 

A loop from   '''3'''   to   '''√{{overline| n }}  ''' will suffice,   but other loops are allowed.

*   [[sequence of primes by Trial Division]]

<br><br>

 

=={{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|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|ActionScript}}==

{

if(n < 2) return false;

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

return true;

 

=={{header|Ada}}==

Test : Natural;

begin

else

Test := 3;

if Item mod Test = 0 then

end if;

Test := Test + 2;

end loop;

 

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:

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

 

 

return true

 

 

 

 

 

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

END FUNCTION

 

' Test and display primes 1 .. 50

FOR n = 1 TO 50

{{out}}

 

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

110 FOR X=0 TO 100

120 IF PRIME(X) THEN PRINT X;

230 NEXT

240 END IF

 

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

20 INPUT "Enter number: ";n

30 IF n>1 THEN GO SUB 1000

1060 NEXT i

1070 RETURN

{{out}}

<pre>

119 is not prime!

137 is prime!</pre>

 

=={{header|bc}}==

define p(n) {

auto i

}

return(1)

 

=={{header|Befunge}}==

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

100000000073

100000000091</pre>

 

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

8 is not a prime number

 

=={{header|D}}==

===Simple Version===

 

return true;

if (n <= 1 || (n & 1) == 0)

return false;

if (n % i == 0)

return false;

return true;

}

 

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

(not (or (< a 2)

More concise, a little bit faster:

(and (> a 1)

A little bit faster:

(and (> a 1)

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)

 

=={{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|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|FunL}}==

 

def

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

 

{{out}}

10000000019

10000000033

 

 

 

=={{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|jq}}==

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

 

=={{header|langur}}==

=== Recursive ===

{{trans|Go}}

val .n = abs(.i)

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

 

return .n ndiv .i and self(.n, .i+2)

}

}

 

 

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

 

=={{header|M4}}==

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

1,

 

isprime(9)

{{out}}

0

1

 

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

 

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|Nim}}==

 

proc prime(a: int): bool =

return false

return true

 

proc prime2(a: int): bool =

 

for i in 2..30:

 

=={{header|Objeck}}==

if(n <= 1) {

return false;

return true;

 

=={{header|OCaml}}==

 

=={{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 */

if(n%p == 0, return(0))

);

1

 

=={{header|Pascal}}==

 

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

 

=={{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|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|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),

 

?-</pre>

 

=={{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|R}}==

 

 

=={{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+$/

 

 

 

=={{header|Rust}}==

match n {

0 | 1 => false,

println!("{} ", i);

}

{{out}}

<pre>2 3 5 7 11 13 17 19 23 29 </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