Sequence of primes by trial division: Difference between revisions
PascalABC.NET
No edit summary |
(PascalABC.NET) |
||
(31 intermediate revisions by 23 users not shown) | |||
Line 30:
{{trans|Python}}
<
R !(a < 2 | any((2 .. Int(a ^ 0.5)).map(x -> @a % x == 0)))
Line 36:
R (0 .< n).filter(i -> prime(i))
print(primes_below(100))</
{{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|Action!}}==
<syntaxhighlight lang="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 PrintPrimes(CARD begin,end)
BYTE notFirst
CARD i
notFirst=0
FOR i=begin TO end
DO
IF IsPrime(i) THEN
IF notFirst THEN
Print(", ")
FI
notFirst=1
PrintC(i)
FI
OD
RETURN
PROC Main()
CARD begin=[2000],end=[3000]
PrintF("Primes in range [%U..%U]:%E",begin,end)
PrintPrimes(begin,end)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Sequence_of_primes_by_trial_division.png Screenshot from Atari 8-bit computer]
<pre>
Primes in range [2000..3000]:
2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137,
2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609,
2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879,
2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999
</pre>
Line 47 ⟶ 99:
Use the generic function Prime_Numbers.Is_Prime, as specified in [[Prime decomposition#Ada]]. The program reads two numbers A and B from the command line and prints all primes between A and B (inclusive).
<
procedure Sequence_Of_Primes is
Line 64 ⟶ 116:
end if;
end loop;
end Sequence_Of_Primes;</
{{out}}
Line 72 ⟶ 124:
=={{header|ALGOL 68}}==
Simple bounded sequence using the "is prime" routine from [[Primality by trial division#ALGOL 68]]
<
MODE ISPRIMEINT = INT;
PROC is prime = ( ISPRIMEINT p )BOOL:
Line 105 ⟶ 157:
print( ( " ", whole( primes[ p ], 0 ) ) )
OD;
print( ( newline ) )</
{{out}}
<pre>
Line 113 ⟶ 165:
=={{header|ALGOL W}}==
Uses the ALGOL W isPrime procedure from the Primality by Trial Division task.
<
% use the isPrime procedure from the Primality by Trial Division task %
logical procedure isPrime ( integer value n ) ; algol "isPrime" ;
Line 144 ⟶ 196:
end
end.</
{{out}}
<pre>
Line 156 ⟶ 208:
=={{header|ALGOL-M}}==
The approach here follows an example given by Edsger Dijkstra in his classic 1969 paper, Notes on Structured Programming. Only odd numbers above 2 are checked for primality, and only the prime numbers previously found (up to the square root of the number under examination) are tested as divisors.
<
BEGIN
Line 206 ⟶ 258:
END
</syntaxhighlight>
{{out}}
Line 222 ⟶ 274:
9: 23
10: 29
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program trialprime.s */
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../constantes.inc"
//.include "../../ficmacros32.inc" @ for debugging developper
/************************************/
/* Initialized data */
/************************************/
.data
szMessPrime: .asciz " is prime.\n"
szMessNotPrime: .asciz " is not prime.\n"
szCarriageReturn: .asciz "\n"
szMessStart: .asciz "Program 32 bits start.\n"
/************************************/
/* UnInitialized data */
/************************************/
.bss
sZoneConv: .skip 24
/************************************/
/* code section */
/************************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrszMessStart
bl affichageMess
ldr r4,iStart @ start number
ldr r5,iLimit @ end number
tst r4,#1
addeq r4,#1
1:
mov r0,r4
ldr r1,iAdrsZoneConv
bl conversion10 @ decimal conversion
ldr r0,iAdrsZoneConv
bl affichageMess
mov r0,r4
bl isPrime
cmp r0,#0
beq 2f
ldr r0,iAdrszMessPrime
bl affichageMess
b 3f
2:
ldr r0,iAdrszMessNotPrime
bl affichageMess
3:
add r4,r4,#2
cmp r4,r5
blt 1b
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
swi 0 @ perform the system call
iAdrsZoneConv: .int sZoneConv
iAdrszMessPrime: .int szMessPrime
iAdrszMessNotPrime: .int szMessNotPrime
iAdrszCarriageReturn: .int szCarriageReturn
iAdrszMessStart: .int szMessStart
iStart: .int 4000000000
iLimit: .int 4000000020
/******************************************************************/
/* test if number is prime */
/******************************************************************/
/* r0 contains the number */
/* r0 return 1 if prime else return 0 */
isPrime:
push {r4,lr} @ save registers
cmp r0,#1 @ <= 1 ?
movls r0,#0 @ not prime
bls 100f
cmp r0,#3 @ 2 and 3 prime
movls r0,#1
bls 100f
tst r0,#1 @ even ?
moveq r0,#0 @ not prime
beq 100f
mov r4,r0 @ save number
mov r1,#3 @ first divisor
1:
mov r0,r4 @ number
bl division
add r1,r1,#2 @ increment divisor
cmp r3,#0 @ remainder = zero ?
moveq r0,#0 @ not prime
beq 100f
cmp r1,r2 @ divisors<=quotient ?
ble 1b @ loop
mov r0,#1 @ return prime
100:
pop {r4,pc} @ restaur registers
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 32 bits start.
4000000001 is not prime.
4000000003 is not prime.
4000000005 is not prime.
4000000007 is prime.
4000000009 is prime.
4000000011 is not prime.
4000000013 is not prime.
4000000015 is not prime.
4000000017 is not prime.
4000000019 is prime.
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">getPrimes: function [upto][
result: new [2]
loop range.step:2 3 upto 'x [
divisible: false
loop 2..inc x/2 'z [
if zero? x%z ->
divisible: true
]
if not? divisible ->
'result ++ x
]
return result
]
print getPrimes 100</syntaxhighlight>
{{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|AsciiDots}}==
Program to generate all prime numbers up to the input (inclusive). This implementation is very inefficient currently since the primality test checks every number from 2 to N rather than checking up to the square root, excluding even numbers from the factor checks, etc.
<syntaxhighlight lang="asciidots">
``warps
%$ABCPR
``outputs all primes up to and including the input
.-#?-A
B-P/$_#$_" "
R-*~
\/
``primality test
/---------------*-\
//-----------{*}*~-+\
///--#1--\ /#1>/ \/ ||
\\*/#2>*-\-~#0*>R ||
/*>*+--++{%}/ \+>C || ``signal to C triggers next number
|\--/>-/| || || ``to be input from for loop
| /-~*--+-------^| ||
| |[<]\ | */ ||
| \-* | | | /--+/
|/-[+]|[*]------+-<1#*
|\1#* \-+-------+----/
| ~---* ^--\
| \---/ | |
\------\ | |
/-----~\ /-----~#0/
P*#2{<}/\-*#2{=}/ ``hardcode <=1 and 2
\---/ \---/
``for loop
``only outputs next number once C receives any input
.-\C#1-*--\ /--B
# /-{+}-+-*--\
1 | /---+----~
*->-*\ \---\|
A{+}>*{-}*-{>}+/
//| \#0/ |
\{*}-------/
</syntaxhighlight>
{{out}}
Output shown for input of 100
<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|ATS}}==
<syntaxhighlight lang="ats">(*
// Lazy-evaluation:
// sieve for primes
Line 294 ⟶ 536:
end // end of [main0]
(* ****** ****** *)</
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SEQUENCE_OF_PRIMES_BY_TRIAL_DIVISION.AWK
BEGIN {
Line 322 ⟶ 564:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 328 ⟶ 570:
25 prime numbers found in range 1-100
</pre>
=={{header|BASIC256}}==
<syntaxhighlight lang="freebasic">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
for i = 101 to 999
if isPrime(i) then print string(i); " ";
next i
end</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
=={{header|Batch File}}==
<syntaxhighlight lang="batch file">
@echo off
::Prime list using trial division
Line 372 ⟶ 633:
set lin=!cnt1:~-5!:
goto:eof
</syntaxhighlight>
{{Out}}
<pre>
Line 406 ⟶ 667:
280: 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889
</pre>
=={{header|bc}}==
<syntaxhighlight lang="bc">l = 100
a[0] = 2
a[o = 1] = 3
for (n = 5; n < l; n += 2) {
for (i = 1; n % (p = a[i]) != 0; ++i) {
if (p * p > n) {
a[++o] = n
break
}
}
}
for (i = 0; i <= o; ++i) a[i]</syntaxhighlight>
=={{header|Befunge}}==
Based on the test in the [[Primality_by_trial_division#Befunge|Primality by trial division]] task, this list all primes between 2 and 1,000,000.
<
v_v#`\*:%*:*84\/*:*84::+<
v#>::48*:*/\48*:*%%!#v_1^
<^+1$_.#<5#<5#<+#<,#<<0:\</
{{out}}
Line 433 ⟶ 710:
=={{header|C}}==
<syntaxhighlight lang="c">
#include<stdio.h>
Line 468 ⟶ 745:
return 0;
}
</syntaxhighlight>
Output :
<pre>
Line 503 ⟶ 780:
=={{header|C sharp}}==
<
using System.Collections.Generic;
using System.Linq;
Line 513 ⟶ 790:
}
static IEnumerable<int> Primes(int limit) => Enumerable.Range(2, limit-
static bool IsPrime(int n) => Enumerable.Range(2, (int)Math.Sqrt(n)-1).All(i => n % i != 0);
}</
{{out}}
<pre>
Line 522 ⟶ 799:
=={{header|C++}}==
<
#include <math.h>
#include <iostream>
Line 553 ⟶ 830:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 564 ⟶ 841:
=={{header|Clojure}}==
<
(:require [clojure.math.numeric-tower :as math]))
Line 582 ⟶ 859:
a))
(println (primes-below 100))</
{{Output}}
Line 588 ⟶ 865:
=={{header|Common Lisp}}==
<
"Compute all primes up to MAX-NUMBER using trial division"
(loop for n from 2 upto max-number
Line 599 ⟶ 876:
(lambda (x) (integerp (/ n x))))
(print (primes-up-to 100))</
Output: <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>
Line 605 ⟶ 882:
=={{header|Crystal}}==
See https://rosettacode.org/wiki/Primality_by_trial_division#Crystal
<
def primep5?(n) # P5 Prime Generator primality test
Line 623 ⟶ 900:
# Create sequence of primes from 1_000_000_001 to 1_000_000_201
n = 1_000_000_001; n.step(to: n+200, by: 2) { |p| puts p if primep5?(p) }</
{{out}}
<pre>1000000007
Line 639 ⟶ 916:
{{trans|Haskell}}
This is a quite inefficient prime generator.
<
std.numeric, std.concurrency;
Line 661 ⟶ 938:
.take(20)
.writeln;
}</
{{out}}
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]</pre>
Line 667 ⟶ 944:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Sequence_of_primes_by_trial_division#Pascal Pascal].
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func prime n .
if n mod 2 = 0 and n > 2
return 0
.
i = 3
while i <= sqrt n
if n mod i = 0
return 0
.
i += 2
.
return 1
.
proc primeSequ first last . sequ[] .
for i = first to last
if prime i = 1
sequ[] &= i
.
.
.
primeSequ 2 100 seq[]
print seq[]
</syntaxhighlight>
=={{header|EchoLisp}}==
===Trial division===
<
(define (is-prime? p)
(cond
Line 678 ⟶ 981:
(for/and ((d [3 5 .. (1+ (sqrt p))] )) (!zero? (modulo p d)))]))
(is-prime? 101) → #t </
===Bounded - List filter ===
<
→ (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)</
=== Unbounded - Sequence filter ===
<
→ # 👓 filter: #sequence [2 3 .. Infinity[
(take f-primes 25)
→ (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)</
=== Unbounded - Stream ===
<
(for ((p [n (+ n 2) .. ] ))
#:break (is-prime? p) => (cons p (+ p 2))))
Line 700 ⟶ 1,003:
(take s-primes 25)
→ (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)</
=== Unbounded - Generator ===
<
(define next
(for ((p [n .. ] )) #:break (is-prime? p) => p ))
Line 712 ⟶ 1,015:
(take g-primes 25)
→ (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)</
=== Unbounded - Background task ===
<
(lib 'bigint)
Line 736 ⟶ 1,039:
1000000000121
1000000000163
*stopped*</
=={{header|EDSAC order code}}==
To save time, the program omits multiples of 2 and 3, and tests 5, 7, 11, 13, ..., the increments being alternately 2 and 4. Division is done implicitly by using wheels. The program stores possible prime divisors in a list, whose size can be edited. If a prime is found, and the list isn't yet full, the prime is added to the list.
Initially, no wheels are active. When the number under test reaches the "milestone" 5^2, the wheel for 5 is activated, and the milestone is updated to 7^2. When that is reached, the wheel for 7 is activated, and the milestone is updated to 11^2; and so on.
In the program as posted, the list of possible divisors holds 30 primes, from 5 to 131. The program finds primes less than 131^2 = 17161, the largest being 17159. Assuming 650 orders per second, this would have taken the original EDSAC about an hour.
<syntaxhighlight lang="edsac">
[List of primes by trial division, for Rosetta Code website.]
[EDSAC program, Initial Orders 2.]
[Division is done implicitly by the use of wheels.
One wheel for each possible prime divisor, up to an editable limit.]
T51K [G parameter: print subroutine, 54 locations.]
P56F [must be even address]
T47K [M parameter: main routine.]
P110F [must be even address]
[============================= M parameter ===============================]
E25KTM
GK
[35-bit values. First clear them completely.
This is done to ensure that the middle bit ("sandwich digit") is zero.]
T#ZPF T2#ZPF T4#ZPF T6#ZPF T8#ZPF
[Back to normal loading]
TZ
[0] PDPF [number under test; initially to 1, pre-inc'd to 5]
[2] P1FPF [increment, alternately 2 and 4]
[4] P12DPF ['milestone', square of prime; initially 25]
[6] PDPF [constant 1]
[8] P3FPF [constant 6]
[17-bit values]
[10] P30F [*EDIT HERE* Number of primes to store (in address field)]
[11] PF [flag < 0 if number is prime; 0 if factor is found]
[12] #F [figure shift]
[13] @F [carriage return]
[14] &F [line feed]
[15] K4096F [null char]
[16] A112@ [A order for list{0}]
[17] T112@ [T order for list{0}]
[18] AF [limit of A order for testing primes]
[19] AF [limit of A order for loading wheels]
[20] TF [limit of T order for storing primes]
[21] O1F [subtract from T order to make A order for previous address]
[22] W1F [add to T order to make U order for next address]
[23] OF [add to A order to make T order for same address]
[24] P2F [to inc an address by 2]
[Enter with acc = 0]
[25] O12@ [set teleprinter to figures]
[Set limits for list of trial prime divisors.
The list contains wheels and negatives of primes, thus:
wheel for 5; -5; wheel for 7; -7; wheel for 11; -11; etc]
A10@ [number of items in prime list]
LD [times 2 words per item (wheel + prime)]
A17@ [add T order for list{0}]
U20@ [store T order for exclusive end of wheels]
S21@ [make A order for inclusive end of primes]
T19@ [store it]
A16@ [load A order for start of lise]
U18@ [store as exclusive end of active wheels]
A2F [inc address, exclusive end of active primes]
T100@ [plant in code]
A17@ [load T order to store first wheel]
T89@ [plant in code]
[Main loop: update increment, alternately 2 and 4]
[Assume acc = 0;]
[38] A8#@ [load 6]
S2#@ [subtract incremet]
T2#@ [store new increment]
[First priority: keep the wheels turning]
A16@ [load order that loads first wheel]
U11@ [set prime flag (any negative value will do)]
[43] U49@ [plant order in code]
S18@ [more wheels to test?]
E66@ [if not, jump with acc = 0]
A18@ [restore after test]
A23@ [make order to store wheel]
T62@ [plant in code]
[49] AF [load wheel]
A2@ [apply current inc as 17-bit 2 or 4]
G62@ [if wheel still < 0, just store updated value]
T1F [wheel >= 0, save in 1F]
S1F [wheel = 0?]
G56@ [no, skip next order]
T11@ [yes, so prime flag := 0]
[56] TF [clear acc]
A49@ [make A order for negative of prime]
A2F
T61@ [plant in code]
A1F [load wheel again]
[61] AF [add negative of prime to set wheel < 0]
[62] TF [store updated wheel]
A49@ [on to next wheel]
A24@
G43@ [always jump, since A < 0]
[Update the number under test. Assume acc = 0.]
[66] A#@ [add incrememnt to number under test]
A2#@
U#@ [store new number]
[Test whether we've reached the "milestone", i.e. number = p^2.]
S4#@ [subtract milestone]
E94@ [if reached milestone, jump with acc = 0]
TF [clear acc]
A11@ [acc < 0 if number is prime, 0 if composite]
E38@ [if composite, loop for next number with acc = 0]
[Here when number is found to be prime.]
TF [clear acc]
A#@ [load number]
TD [copy number 0D for printing]
[77] A77@
GG [call print routine, clears acc]
O13@O14@ [print CR, LF]
[If list of primes isn't yet full, store the prime just found.
It's slightly more convenient to store the negative of the prime.
Also, the wheel is initialized to the negative of the prime.]
A89@ [load T order to store ]
S20@ [compare with end of list]
E38@ [if list is full, loop with acc = 0]
A20@ [restore acc after test]
A22@ [make U order for wheel + 1, i.e. for prime]
T88@ [plant in code]
S@ [load negative of latest prime]
[88] UF [store in list]
[89] TF [initialize wheel for this prime]
A89@ [inc address by 2 for next time]
A24@
T89@
E38@ [loop with acc = 0]
[Here when number tested equals the "milestone" p^2 (p prime).
We need to activate the wheel for the prime p,
and update the milestone to the next prime after p.]
[Assume acc = 0.]
[94] A100@ [load A order below]
S19@ [test against A order for end of list]
E110@ [if reached end of list, exit]
A19@ [restore acc after test]
A24@ [inc address in A order]
T100@ [plant in next order]
[100] AF [load negative of prime from list]
TF [to 0F]
HF [to mult reg]
VF [acc := square of prime scaled by 2^(-32)]
R1F [scale by 2^(-34) for 35-bit value]
T4#@ [update]
A18@ [start testing next prime wheel]
A24@
T18@
E38@ [loop with acc = 0]
[Here on exit from program]
[110] O15@ [print null to flush printer buffer]
[111] ZF [stop]
[Array of wheels and primes, immediately after program code]
[112]
[============================ G parameter ==================================]
[Modified library subroutine P7.]
[Prints signed integer; up to 10 digits, left-justified.]
[Input: 0D = integer,]
[54 locations. Load at even address. Workspace 4D.]
E25KTG
GKA3FT42@A49@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@
TFH17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4D
A49@T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFSFL8FT4DE39@
[========================= M parameter again ===============================]
E25KTM
GK
E25Z [define entry point]
PF [acc = 0 on entry]
</syntaxhighlight>
{{out}}
<pre>
5
7
11
13
[...]
17047
17053
17077
17093
17099
17107
17117
17123
17137
17159
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 812 ⟶ 1,304:
end
</syntaxhighlight>
{{out}}
<pre>
Line 827 ⟶ 1,319:
=={{header|Elena}}==
ELENA
<
import system'routines;
import system'math;
isPrime =
(n => new Range(2,(n.sqrt() - 1).RoundedInt).allMatchedBy::(i => n.mod
Primes =
(n => new Range(2, n - 2).filterBy
public program()
{
console.printLine(Primes(100))
}</
{{out}}
<pre>
Line 848 ⟶ 1,340:
=={{header|Elixir}}==
<
def sequence do
Stream.iterate(2, &(&1+1)) |> Stream.filter(&is_prime/1)
Line 862 ⟶ 1,354:
end
IO.inspect Prime.sequence |> Enum.take(20)</
{{out}}
Line 870 ⟶ 1,362:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM PRIME_GENERATOR
Line 886 ⟶ 1,378:
END LOOP
END PROGRAM
</syntaxhighlight>
You must press Ctrl+Break to stop the program.
{{out}}
Line 909 ⟶ 1,401:
=={{header|F Sharp}}==
<
(*
Nigel Galloway April 7th., 2017.
Line 918 ⟶ 1,410:
yield n; yield! fg (Seq.cache(Seq.filter (fun g->g%n<>0) (Seq.skip 1 ng)))}
fg (Seq.initInfinite(id)|>Seq.skip 2)
</syntaxhighlight>
Let's print the sequence Prime[23] to Prime[42].
{{out}}
<
[23..42] |> Seq.iter(fun n->printf "%d " (Seq.item n SofE))
</syntaxhighlight>
<pre>
89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191
Line 929 ⟶ 1,421:
=={{header|Factor}}==
<
math.ranges prettyprint sequences ;
Line 943 ⟶ 1,435:
! Show the first fifteen primes.
15 primes ltake list>array .</
{{out}}
<pre>
Line 950 ⟶ 1,442:
=={{header|FileMaker}}==
<
Set Error Capture [On]
Allow User Abort [Off]
Line 1,023 ⟶ 1,515:
End If
#
</syntaxhighlight>
=={{header|Forth}}==
This program stores the generated primes into a user allocated array and uses the primes generated so far to test divisibility of subsequent candidates. In FORTH, the PAD can be used as a large memory area that is always available, and the main .primes word makes use of that.
<syntaxhighlight lang="forth">
variable p-start \ beginning of prime buffer
variable p-end \ end of prime buffer
Line 1,067 ⟶ 1,559:
i @ 5 .r
cell +loop ;
</syntaxhighlight>
{{Out}}
<pre>
Line 1,103 ⟶ 1,595:
This method avoids considering multiples of two and three, leading to the need to pre-load array PRIME and print the first few values explicitly rather than flounder about with special startup tricks. Even so, in order not to pre-load with 7, and to correctly start the factor testing with 5, the first few primes are found with some wasted effort because 5 is not needed at the start. Storing the primes as found has the obvious advantage of enabling divisions only by prime numbers, but care with the startup is needed to ensure that primes have indeed been stored before they are called for.
<syntaxhighlight lang="fortran">
CONCOCTED BY R.N.MCLEAN, APPLIED MATHS COURSE, AUCKLAND UNIVERSITY, MCMLXXI.
INTEGER ENUFF,PRIME(44)
Line 1,148 ⟶ 1,640:
40 IF (N - 32767) 10,41,41
41 WRITE (6,34) (ALINE(I), I = 1,LL)
END</
Start of output:
Line 1,166 ⟶ 1,658:
=={{header|FreeBASIC}}==
<
Function isPrime(n As Integer) As Boolean
Line 1,188 ⟶ 1,680:
Print : Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,204 ⟶ 1,696:
=={{header|Go}}==
An unbounded cascading filtering method using channels, adapted from the classic concurrent prime sieve example in the "Try Go" window at http://golang.org/, improved by postponing the initiation of the filtering by a prime until the prime's square is seen in the input.
<
import "fmt"
Line 1,258 ⟶ 1,750:
}
fmt.Println()
}</
{{out}}
<pre>
Line 1,264 ⟶ 1,756:
</pre>
A simple iterative method, also unbounded and starting with 2.
<
import "fmt"
Line 1,295 ⟶ 1,787:
}
fmt.Println()
}</
{{out}}
<pre>
Line 1,303 ⟶ 1,795:
=={{header|Haskell}}==
The most basic:
<
With trial division emulated by additions (the seeds of Sieve):
<
With recursive filtering (in wrong order, from bigger to smaller natural numbers):
<
With iterated sieving (in right order, from smaller to bigger primes):
<
A proper [[Primality by trial division#Haskell|primality testing by trial division]] can be used to produce short ranges of primes more efficiently:
<
The standard optimal trial division version has <code>isPrime</code> in the above inlined:
<
primes = 2 : [n | n <- [3..], foldr (\p r-> p*p > n || rem n p > 0 && r)
True primes]</
It is easy to amend this to test only odd numbers by only odd primes, or automatically skip the multiples of ''3'' (also, ''5'', etc.) by construction as well (a ''wheel factorization'' technique):
<
True (drop 1 primes)]
= [2,3,5] ++ [n | n <- scanl (+) 7 (cycle [4,2]),
foldr (\p r-> p*p > n || rem n p > 0 && r)
True (drop 2 primes)]
-- = [2,3,5,7] ++ [n | n <- scanl (+) 11 (cycle [2,4,2,4,6,2,6,4]), ... (drop 3 primes)]</
It is also easy to extend the above in generating the factorization wheel automatically as follows:
<
wheelGen :: Int -> ([Int],Int,[Int])
wheelGen n = loop 1 3 [2] [2] where
Line 1,359 ⟶ 1,851:
| any ((==) 0 . rem n)
(takeWhile ((<= n) . flip (^) 2) bps) = xtrprms (n + g) gs'
| otherwise = n : xtrprms (n + g) gs'</
This is likely about the fastest of the trial division prime generators at just a few seconds to generate the primes up to ten million, which is about the limit of its practical range. An incremental Sieve of Eratosthenes sieve will extend the useful range about ten times this and isn't that much more complex.
Line 1,365 ⟶ 1,857:
===Sieve by trial division===
The classic David Turner's 1983 (1976? 1975?) SASL code repeatedly ''sieves'' a stream of candidate numbers from those divisible by a prime at a time, and works even for unbounded streams, thanks to lazy evaluation:
<
where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]
-- map head
-- . iterate (\(p:xs) -> filter ((> 0).(`rem` p)) xs) $ [2..]</
As shown in Melissa O'Neill's paper [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced.
Line 1,377 ⟶ 1,869:
===Bounded sieve by trial division===
Bounded formulation has normal trial division complexity, because it can stop early via an explicit guard:
<
where
sieve (p:xs) | p*p > m = p : xs
| otherwise = p : sieve [x | x <- xs, rem x p /= 0]
-- (\(a,b:_) -> map head a ++ b) . span ((< m).(^2).head)
-- $ iterate (\(p:xs) -> filter ((>0).(`rem`p)) xs) [2..m]</
===Postponed sieve by trial division===
{{trans|Racket}}
To make it unbounded, the guard cannot be simply discarded. The firing up of a filter by a prime should be ''postponed'' until its ''square'' is seen amongst the candidates (so a bigger chunk of input numbers are taken straight away as primes, between each opening up of a new filter, instead of just one head element in the non-postponed algorithm):
<
where
sieve ~(p:ps) (x:xs) = x : after (p*p) xs
Line 1,394 ⟶ 1,886:
| otherwise = f (x:xs)
-- fix $ concatMap (fst.fst) . iterate (\((_,t),p:ps) ->
-- (span (< head ps^2) [x | x <- t, rem x p > 0], ps)) . (,) ([2,3],[4..])</
<code>~(p:ps)</code> is a lazy pattern: the matching will be delayed until any of its variables are actually needed. Here it means that on the very first iteration the head of <code>primesPT</code> will be safely accessed only after it is already defined (by <code>x : after (p*p) ...</code>).
Line 1,400 ⟶ 1,892:
Note that the above introduced laziness for the evaluation of the head of the base primes list in order to avoid a race isn't necessary for the usual method of just introducing the first of the base primes before starting the computation as follows (use the same `wheelGen` as above for this wheel factorized version):
<
primesPTDW() = -- causes mucho allocation of deferred thunks!
wheelPrimes ++ _Y ((firstSievePrime :) . sieve cndts) where
Line 1,408 ⟶ 1,900:
q = bp * bp
after (x:xs') | x >= q = sieve (filter ((> 0) . (`rem` bp)) xs') bps'
| otherwise = x : after xs'</
However, these postponed solutions are slower than the last of the basic trial division prime generators as the (nested) filters add greatly the the deferred "thunks" stored to the heap rather than the more direct (and more strict) determination of whether a number is prime as it's output.
Line 1,414 ⟶ 1,906:
===Segmented Generate and Test===
Explicating the run-time list of ''filters'' (created implicitly by the sieves above) as a list of ''factors to test by'' on each segment between the consecutive squares of primes (so that no testing is done prematurely), and rearranging to avoid recalculations, leads to the following:
<
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST)
where
sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2]
++ sieve (q+2) (head ps^2) (tail ps) ft</
<code>inits</code> makes a stream of (progressively growing) prefixes of an input stream, starting with an empty prefix, here making the <code>fs</code> parameter to get a sequence of values <code>[], [3], [3,5], ...</code>.
Line 1,430 ⟶ 1,922:
Implementation:
<
try=. i.&.(p:inv) %: >./ y
candidate=. (y>1)*y=<.y
y #~ candidate*(y e.try) = +/ 0= try|/ y
)</
Example use:
<
1000003 1000033 1000037 1000039 1000081 1000099</
Note that this is a filter - it selects values from its argument which are prime. If no suitable values are found the resulting sequence of primes will be empty.
Line 1,449 ⟶ 1,941:
=={{header|Java}}==
{{works with|Java|8}}
<
public class Test {
Line 1,473 ⟶ 1,965:
getPrimes(0, 100).forEach(p -> System.out.printf("%d, ", p));
}
}</
<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>
Line 1,481 ⟶ 1,973:
This entry uses is_prime/0 as defined at [[Primality_by_trial_division#jq]].
<
def primes(m; n):
([m,2] | max) as $m
Line 1,487 ⟶ 1,979:
elif $m == 2 then 2, primes(3;n)
else (1 + (2 * range($m/2 | floor; (n + 1) /2 | floor))) | select( is_prime )
end;</
'''Examples:'''
<syntaxhighlight lang
<
3
5
7</
Produce an array of primes, p, satisfying 50 <= p <= 99:
<syntaxhighlight lang
[53,59,61,67,71,73,79,83,89,97]
Line 1,504 ⟶ 1,996:
I've chosen to solve this task by creating a new iterator type, <tt>TDPrimes</tt>. <tt>TDPrimes</tt> contains the upper limit of the sequence. The iteration state is the list of computed primes, and the item returned with each iteration is the current prime. The core of the solution is the <tt>next</tt> method for <tt>TDPrimes</tt>, which computes the next prime by trial division of the previously determined primes contained in the iteration state.
<
uplim::T
end
Line 1,521 ⟶ 2,013:
end
println("Primes ≤ 100: ", join((p for p in TDPrimes(100)), ", "))</
{{out}}
Line 1,527 ⟶ 2,019:
=={{header|Kotlin}}==
<
fun isPrime(n: Int): Boolean {
Line 1,553 ⟶ 2,045:
if (count % 15 == 0) println()
}
}</
{{out}}
Line 1,582 ⟶ 2,074:
=={{header|Lambdatalk}}==
<
{def prime
{def prime.rec
Line 1,599 ⟶ 2,091:
{map prime {serie 9901 10000 2}}
-> 9901 9907 9923 9929 9931 9941 9949 9967 9973
</syntaxhighlight>
More to see in [http://epsilonwiki.free.fr/lambdaway/?view=primes2]
=={{header|LFE}}==
This version is inspired by PicoLisp, however instead of using the algorithm from the paper "Lazy wheel sieves and spirals of primes", this program uses a static 2,3,5,7,11 factorization wheel. Since the diminishing returns of factor wheels hit hard after 11, it's arguably better to use a precomputed fixed sized wheel. Like the PicoLisp version, this code also uses a separate thread to serve the primes.
<syntaxhighlight lang="lisp">
(defmodule tdwheel
(export
(primes 0) (gen 1) (next 1)))
(defun +wheel-2x3x5x7x11+ ()
#B( 12 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2
4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4
6 2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4
6 2 6 6 4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2
4 12 2 6 4 2 6 4 6 12 2 4 2 4 8 6 4 6 2 4 6 2 6 10
2 4 6 2 6 4 2 4 2 10 2 10 2 4 6 6 2 6 6 4 6 6 2 6
4 2 6 4 6 8 4 2 6 4 8 6 4 6 2 4 6 8 6 4 2 10 2 6
4 2 4 2 10 2 10 2 4 2 4 8 6 4 2 4 6 6 2 6 4 8 4 6
8 4 2 4 2 4 8 6 4 6 6 6 2 6 6 4 2 4 6 2 6 4 2 4
2 10 2 10 2 6 4 6 2 6 4 2 4 6 6 8 4 2 6 10 8 4 2 4
2 4 8 10 6 2 4 8 6 6 4 2 4 6 2 6 4 6 2 10 2 10 2 4
2 4 6 2 6 4 2 4 6 6 2 6 6 6 4 6 8 4 2 4 2 4 8 6
4 8 4 6 2 6 6 4 2 4 6 8 4 2 4 2 10 2 10 2 4 2 4 6
2 10 2 4 6 8 6 4 2 6 4 6 8 4 6 2 4 8 6 4 6 2 4 6
2 6 6 4 6 6 2 6 6 4 2 10 2 10 2 4 2 4 6 2 6 4 2 10
6 2 6 4 2 6 4 6 8 4 2 4 2 12 6 4 6 2 4 6 2 12 4 2
4 8 6 4 2 4 2 10 2 10 6 2 4 6 2 6 4 2 4 6 6 2 6 4
2 10 6 8 6 4 2 4 8 6 4 6 2 4 6 2 6 6 6 4 6 2 6 4
2 4 2 10 12 2 4 2 10 2 6 4 2 4 6 6 2 10 2 6 4 14 4 2
4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 12 2))
(defun next (pid)
(! pid `#(next ,(self)))
(receive (x x)))
(defun primes ()
(spawn (MODULE) 'gen '((2 3 5 7 11))))
(defun gen (primes)
(receive
(`#(next ,sender)
(case primes
((list p)
(! sender p)
(divloop 1 0 (+wheel-2x3x5x7x11+)))
((cons p ps)
(! sender p)
(gen ps))))))
(defun divloop (n j wheel)
(receive
(`#(next ,sender)
(let [((tuple n' j') (next-prime n j wheel))]
(! sender n')
(divloop n' j' wheel)))))
(defun next-prime (n0 j wheel)
(let [
(n (+ n0 (binary:at wheel j)))
(j' (if (=:= j (- (byte_size wheel) 1))
0
(+ j 1)))
]
(if (td-prime? n 1 0 wheel)
(tuple n j')
(next-prime n j' wheel))))
(defun td-prime? (n d0 j wheel) ; 2,3,5,7,11 does not divide n
(let [(d (+ d0 (binary:at wheel j)))]
(cond
((> (* d d) n)
'true)
((=:= 0 (rem n d))
'false)
(else
(td-prime?
n
d
(if (=:= j (- (byte_size wheel) 1)) 0 (+ j 1))
wheel)))))
</syntaxhighlight>
Driver code:
<syntaxhighlight lang="lisp">
#!/usr/local/bin/lfescript
(defun show-primes (n)
(show-primes n (tdwheel:primes)))
(defun show-primes
((0 _) (io:format "~n"))
((n pid)
(lfe_io:format "~b " (list (tdwheel:next pid)))
(show-primes (- n 1) pid)))
(defun show-table (limit)
(io:format "n\tnth prime\n")
(show-table limit 1 1 (tdwheel:primes)))
(defun show-table (limit k goal pid)
(cond
((> k limit)
'ok)
((=:= k goal)
(let [(p (tdwheel:next pid))]
(io:format "~b\t~b\n" (list goal p))
(show-table limit (+ k 1) (* goal 10) pid)))
(else
(tdwheel:next pid) ; discard result
(show-table limit (+ k 1) goal pid))))
(defun main (_)
(show-primes 25)
(show-table 100000))
</syntaxhighlight>
{{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
n nth prime
1 2
10 29
100 541
1000 7919
10000 104729
100000 1299709
</pre>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
print "Rosetta Code - Sequence of primes by trial division"
print: print "Prime numbers between 1 and 50"
Line 1,624 ⟶ 2,241:
isPrime=1
end function
</syntaxhighlight>
{{out}}
<pre>
Line 1,654 ⟶ 2,271:
=={{header|Lua}}==
<
function isprime (x)
if x < 2 then return false end
Line 1,686 ⟶ 2,303:
-- Main procedure
show(primes(100))
show(primes(50, 150))</
{{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
53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149</pre>
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module primes_by_trial_division{
inventory Known1=2@, 3@
Global IsPrime=lambda Known1 (x as decimal) -> {
=false
if exist(Known1, x) then =true : exit
if x<=5 OR frac(x) then {if x == 2 OR x == 3 OR x == 5 then Append Known1, x : =true
Break}
if frac(x/2) else exit
if frac(x/3) else exit
x1=sqrt(x):d = 5@
do
if frac(x/d) else exit
d += 2: if d>x1 then Append Known1, x : =true : exit
if frac(x/d) else exit
d += 4: if d<= x1 else Append Known1, x : =true: exit
always
}
takePrimes=lambda IsPrime, i=2 (n)-> {
flush
while n>0: if isPrime(i) then data i: n--
i++:end while
=array([])
}
report "["+takePrimes(10)#str$(", ")+"]"
m=takePrimes(90) // skip 90 primes
report "["+takePrimes(100)#str$(", ")+"]"
}
primes_by_trial_division
</syntaxhighlight>
{{out}}
<pre>
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
[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, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223]
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
primeq[1]:=False
primeq[2]:=True
Line 1,698 ⟶ 2,353:
AllTrue[Range[2,Sqrt[n]+1],Mod[n,#]!=0&]
]
Select[Range[100],primeq]</
{{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|MATLAB}}==
<
list = (2:lastNumber); %Construct list of numbers
Line 1,717 ⟶ 2,372:
primeList = [primeList list]; %The rest of the numbers in the list are primes
end</
sieveOfEratosthenes(30)
Line 1,726 ⟶ 2,381:
=={{header|Nim}}==
{{trans|Kotlin}}
<
func isPrime(n: int): bool =
Line 1,748 ⟶ 2,403:
if count mod 15 == 0:
write(stdout, "\n")
echo()</
{{out}}
Line 1,774 ⟶ 2,429:
1993 1997 1999
</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="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
let seq_prime =
Seq.ints 2 |> Seq.filter is_prime
let () =
seq_prime |> Seq.take 25 |> Seq.iter (Printf.printf " %u") |> print_newline</syntaxhighlight>
{{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|Oforth}}==
Line 1,779 ⟶ 2,451:
isPrime function is from Primality by trial division page
<
=={{header|PARI/GP}}==
<
if(n < 4, return(n > 1)); /* Handle negatives */
forprime(p=2,sqrt(n),
Line 1,790 ⟶ 2,462:
};
select(trial, [1..100])</
=={{header|Pascal}}==
{{libheader|primTrial}} {{works with|Free Pascal}}
Hiding the work in a existing unit.
<syntaxhighlight lang="pascal">
program PrimeRng;
uses
Line 1,807 ⟶ 2,479:
write(Range[i]:12);
writeln;
end.</
;output:
<pre> 1000000007 1000000009 1000000021 1000000033 1000000087 1000000093 1000000097</pre>
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
##
function IsPrime(n: integer) := (2..n.Sqrt.Round).All(i -> n.NotDivs(i));
(2..100).Where(IsPrime).Println
</syntaxhighlight>
{{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|Perl}}==
<syntaxhighlight lang
use enum <false true>;
sub isprime ($n) {
return false unless $n % $i and $n % ($i+2);
true
}
{{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
Line 1,831 ⟶ 2,517:
=={{header|Phix}}==
Exact copy of [[Primality_by_trial_division#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>
Line 1,844 ⟶ 2,530:
<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>
Line 1,851 ⟶ 2,537:
=={{header|PicoLisp}}==
<
(or
(= N 2)
Line 1,865 ⟶ 2,551:
(filter prime? (range A B)) )
(println (primeseq 50 99))</
{{out}}
<pre>(53 59 61 67 71 73 79 83 89 97)</pre>
Line 1,873 ⟶ 2,559:
This is based on the wheel sieve Mark 1 in the paper, where candidates are taken from increasing size factorization wheels, where the next wheel of increasing size is used after the current wheel is completely "rolled."
<syntaxhighlight lang="picolisp">
(de comma_fmt (N) (format N 0 "." ","))
Line 1,914 ⟶ 2,600:
(prinl "The 10,001st prime is " (comma_fmt (primes T)))
(bye)
</syntaxhighlight>
{{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 101 103 107 109 113 127
The 10,001st prime is 104,743
</pre>
=={{header|PL/I-80}}==
<syntaxhighlight lang="PL/I">
/* Prime Number Generator in PLI-80
*
* The logic closely follows an example program by Edsger
* W. Dijkstra in his classic 1969 paper, "Notes on Structured
* Programming." Only odd numbers are checked for primality,
* and only the prime numbers previously found (up to the
* square root of the number under examination) are tested
* as divisors.
*/
primes:
proc options (main);
%replace
maxprimes by 3500, /* practical limit before overflow */
false by '0'b,
true by '1'b;
dcl
p(1:maxprimes) fixed binary(15),
divisible bit(1),
dummy char(1),
(i, k, m, n, s, nprimes, divisor) fixed binary(15);
put skip list ('How many primes do you want? ');
get list (nprimes);
if nprimes > maxprimes then
do;
nprimes = maxprimes;
put skip list ('Only generating',maxprimes,' primes.');
put skip list ('Press CR to continue.');
get edit (dummy) (a);
end;
/* initialize p with first prime number and display it */
p(1) = 2;
put skip list (p(1));
i = 1; /* count of prime numbers found so far */
k = 1; /* index of largest prime <= sqrt of n */
n = 3; /* current number being checked */
do while (i < nprimes);
s = p(k) * p(k);
if s <= n then k = k + 1;
divisible = false;
m = 1; /* index into primes already found */
do while ((m <= k) & (divisible = false));
divisor = p(m); /* can't put p(m) directly into mod()! */
if mod(n, divisor) = 0 then divisible = true;
m = m + 1;
end;
if divisible = false then /* found a prime */
do;
i = i + 1;
p(i) = n;
put list (n);
end;
n = n + 2; /* advance to next odd number */
end;
put skip list ('All done. Goodbye.');
end;
</syntaxhighlight>
{{out}}
<pre>
How many primes do you want? 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
* * *
419 421 431 433 439 443 449 457
461 463 467 479 487 491 499 503
509 521 523 541
All done. Goodbye.
</pre>
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function eratosthenes ($n) {
if($n -ge 1){
Line 1,945 ⟶ 2,708:
}
"$(sieve-start-end 100 200)"
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 1,953 ⟶ 2,716:
=={{header|Prolog}}==
Creates a 2,3,5 factorization wheel to eliminate the majority of divisors and prime candidates before filtering.
<syntaxhighlight lang="prolog">
wheel235(L) :-
W = [6, 4, 2, 4, 2, 4, 6, 2 | W],
Line 1,975 ⟶ 2,738:
roll235wheel(Limit, Candidates),
include(prime235, Candidates, Primes).
</syntaxhighlight>
{{Out}}
<pre>
Line 1,989 ⟶ 2,752:
=={{header|PureBasic}}==
<
#SPC=Chr(32)
#TB=~"\t"
Line 2,037 ⟶ 2,800:
Print(~"\nPrimes= "+Str(*count\i))
Input()
EndIf</
{{out}}
<pre>Input (n1<n2 & n1>0)
Line 2,059 ⟶ 2,822:
=={{header|Python}}==
Using the basic ''prime()'' function from: [http://rosettacode.org/wiki/Primality_by_trial_division#Python "Primality by trial division"]
<syntaxhighlight lang="python">
def prime(a):
return not (a < 2 or any(a % x == 0 for x in xrange(2, int(a**0.5) + 1)))
Line 2,065 ⟶ 2,828:
def primes_below(n):
return [i for i in range(n) if prime(i)]
</syntaxhighlight>
{{out}}
<pre>>>> primes_below(100)
Line 2,071 ⟶ 2,834:
===Fun With Lists===
<
primelist = []
def primer(n):
for d in primelist:
break
if n % d == 0:
return
primelist.append(n)
for vv in range(
primer(vv)
print(len(primelist))
print(*primelist)</
{{out}}
<pre>
=={{header|Quackery}}==
Line 2,099 ⟶ 2,860:
Make a nest of primes less than n.
<
[ i^ isprime if
[ i^ join ] ] ] is primes< ( n --> [ )
100 primes< echo</
{{Out}}
Line 2,117 ⟶ 2,878:
This example uses infinite lists (streams) to implement a sieve algorithm that produces all prime numbers.
<
(define nats (cons 1 (map add1 nats)))
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l))
(define (sieve l) (cons (first l) (sieve (sift (first l) (rest l)))))
(define primes (sieve (rest nats)))
(!! (take 25 primes))</
==== Optimized with postponed processing ====
Line 2,128 ⟶ 2,889:
Since a prime's multiples that count start from its square, we should only add them when we reach that square.
<
(define nats (cons 1 (map add1 nats)))
(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l))
Line 2,137 ⟶ 2,898:
(λ(t) (sieve (sift (car ps) t) (cdr ps))))))
(define primes (sieve (cdr nats) primes))
(!! (take 25 primes))</
=== Using threads and channels ===
Line 2,143 ⟶ 2,904:
Same algorithm as above, but now using threads and channels to produce a channel of all prime numbers (similar to newsqueak). The macro at the top is a convenient wrapper around definitions of channels using a thread that feeds them.
<
(define-syntax (define-thread-loop stx)
(syntax-case stx ()
Line 2,160 ⟶ 2,921:
(let ([x (channel-get c)]) (out! x) (set! c (sift x c))))
(define primes (let ([ns (nats)]) (channel-get ns) (sieve ns)))
(for/list ([i 25] [x (in-producer (λ() (channel-get primes)))]) x)</
=== Using generators ===
Line 2,166 ⟶ 2,927:
Yet another variation of the same algorithm as above, this time using generators.
<
(require racket/generator)
(define nats (generator () (for ([i (in-naturals 1)]) (yield i))))
Line 2,175 ⟶ 2,936:
(generator () (let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g))))))
(define primes (begin (nats) (sieve nats)))
(for/list ([i 25] [x (in-producer primes)]) x)</
=={{header|Raku}}==
(formerly Perl 6)
Here is a straightforward implementation of the naive algorithm.
<syntaxhighlight lang="raku"
say @primes[^100];</
{{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 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</pre>
Line 2,192 ⟶ 2,953:
Usage note: by using a negative number (for the program's argument), the list of primes is suppressed, but the prime count is still shown.
<
parse arg n . /*get optional number of primes to find*/
if n=='' | n=="," then n= 26 /*Not specified? Then use the default.*/
Line 2,209 ⟶ 2,970:
end /*j*/ /* [↑] only display N number of primes*/
/* [↓] display number of primes found.*/
say # ' primes found.' /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default input: <tt> 26 </tt>}}
<pre>
Line 2,244 ⟶ 3,005:
This version shows how the REXX program may be optimized further by extending the list of low primes and
<br>the special low prime divisions (the <big>'''//'''</big> tests, which is the ''remainder'' when doing division).
<
parse arg N . /*get optional number of primes to find*/
if N=='' | N=="," then N= 26 /*Not specified? Then assume default.*/
Line 2,270 ⟶ 3,031:
end /*j*/ /* [↑] only display N number of primes*/
/* [↓] display number of primes found.*/
say # ' primes found.' /*stick a fork in it, we're all done. */</
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}} <br><br>
=={{header|Ring}}==
<
for i = 1 to 100
if isPrime(i) see "" + i + " " ok
Line 2,288 ⟶ 3,049:
next
return true
</syntaxhighlight>
=={{header|RPL}}==
<code>PRIM?</code> is defined at [[Primality by trial division#RPL|Primality by trial division]]
≪ { } 2 ROT '''FOR''' n
'''IF''' n <span style="color:blue">PRIM?</span> THEN n + '''END'''
'''NEXT'''
≫ '<span style="color:blue">PRIMES</span>' STO
50 <span style="color:blue">PRIMES</span>
{{out}}
<pre>
1: { 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 }
</pre>
=={{header|Ruby}}==
The Prime class in the standard library has several Prime generators. In some methods it can be specified which generator will be used. The generator can be used on it's own:
<
pg = Prime::TrialDivisionGenerator.new
p pg.take(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
p pg.next # => 31</
===By Trial Division w/Prime Generator===
See https://rosettacode.org/wiki/Primality_by_trial_division#Ruby
<
# 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
Line 2,315 ⟶ 3,089:
# Create sequence of primes from 1_000_000_001 to 1_000_000_201
n = 1_000_000_001; n.step(n+200, 2) { |p| puts p if primep5?(p) }</
{{out}}
<pre>1000000007
Line 2,329 ⟶ 3,103:
=={{header|Rust}}==
<
fn is_prime(number: u32) -> bool {
#[allow(clippy::cast_precision_loss)]
Line 2,349 ⟶ 3,123:
);
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,357 ⟶ 3,131:
=={{header|S-BASIC}}==
<
comment
Prime number generator in S-BASIC. Only odd numbers are
Line 2,395 ⟶ 3,169:
if s <= n then k = k + 1
divisible = false
m = 1 rem index
while (m <= k) and (divisible = false) do
begin
Line 2,412 ⟶ 3,186:
print "All done. Goodbye"
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,423 ⟶ 3,197:
===Odds-Only "infinite" primes generator using Streams and Co-Inductive Streams===
Using Streams, [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf the "unfaithful sieve"], i.e. '''sub-optimal trial division sieve'''.
<
Stream.cons(nums.head, sieve((nums.tail).filter(_ % nums.head != 0)))
val primes = 2 #:: sieve(Stream.from(3, 2))
println(primes take 10 toList) // //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
println(primes takeWhile (_ < 30) toList) //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</
{{out}}Both println statements give the same results:
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</pre>
Line 2,436 ⟶ 3,210:
=={{header|Sidef}}==
Using the ''is_prime()'' function from: [http://rosettacode.org/wiki/Primality_by_trial_division#Sidef "Primality by trial division"]
<
var (counter, number) = (0, 0);
while (counter < amount) {
Line 2,447 ⟶ 3,221:
}
prime_seq(100, {|p| say p}); # prints the first 100 primes</
=={{header|Spin}}==
Line 2,455 ⟶ 3,229:
{{works with|HomeSpun}}
{{works with|OpenSpin}}
<
_clkmode = xtal1+pll16x
_clkfreq = 80_000_000
Line 2,477 ⟶ 3,251:
waitcnt(_clkfreq + cnt)
ser.stop</
{{Out}}
<pre>
Line 2,484 ⟶ 3,258:
=={{header|Swift}}==
<
extension SequenceType {
Line 2,506 ⟶ 3,280:
}
return pastPrimes.last
}</
===Simple version===
{{works with|Swift 2 and Swift 3}}
<
func trialPrimes(_ max:Int){
Line 2,529 ⟶ 3,303:
trialPrimes(100)
print(primes)</
{{out}}
<pre>
Line 2,537 ⟶ 3,311:
=={{header|Tailspin}}==
Simplest version
<
templates ifPrime
def n: $;
[2..~$n -> $n
end ifPrime
Line 2,549 ⟶ 3,323:
100 -> primes -> '$;
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 2,557 ⟶ 3,331:
=={{header|Tcl}}==
As we're generating a sequence of primes, we can use that sequence of primes to describe what we're filtering against.
<
proc havePrime n {
global primes
Line 2,572 ⟶ 3,346:
}
}
puts ""</
{{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|uBasic/4tH}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="uBasic/4tH">' Print all primes from 101 to 999
For i = 101 To 999
If FUNC(_isPrime(i)) Then
Print Using "__# "; i;
EndIf
Next
Print : End
_isPrime
Param (1)
Local (2)
If a@ < 2 Then Return (0)
If a@ = 2 Then Return (1)
If (a@ % 2) = 0 Then Return (0)
b@ = FUNC(_Sqrt(a@, 0))
For c@ = 3 To b@ Step 2
If (a@ % c@) = 0 Then Unloop : Return (0)
Next
Return (1)
_Sqrt
Param (2)
Local (2)
If a@ = 0 Return (0)
c@ = Max(Shl(Set(a@, a@*(10^(b@*2))), -10), 1024)
Do
d@ = (c@+a@/c@)/2
While c@ > d@
c@ = d@
Loop
Return (c@)</syntaxhighlight>
{{Out}}
<pre>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
0 OK, 0:136</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Vlang">
import math
fn main() {
for idx in 1..101 {if is_prime(idx) {println("${idx}")}}
}
fn is_prime(num int) bool {
if num < 2 {return false}
if num < 4 {return true}
if num % 2 == 0 {return false}
for idx := 3; idx <= math.sqrt(num); idx += 2 {
if num % idx == 0 {return false}
}
return true
}
</syntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
Using a simple generator.
<
var primeSeq = Fiber.new {
Line 2,609 ⟶ 3,451:
if (count%15 == 0) System.print()
if (count == limit) break
}</
{{out}}
Line 2,635 ⟶ 3,477:
1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
int N;
for N:= 2 to 100 do
if IsPrime(N) then
[IntOut(0, N); ChOut(0, ^ )]</syntaxhighlight>
{{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|Yabasic}}==
<syntaxhighlight lang="yabasic">sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
for i = 101 to 999
if isPrime(i) print str$(i), " ";
next i
end</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
=={{header|zkl}}==
The code in [[Extensible prime generator#zkl]] is a much better solution to this problem.
{{trans|Python}}
<
(p>=2) and (not [2 .. p.toFloat().sqrt()].filter1('wrap(n){ p%n==0 }))
}
fcn primesBelow(n){ [0..n].filter(isPrime) }</
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.
<
{{out}}
<pre>
|