Rosetta Code

Extensible prime generator: Difference between revisions

Page Discussion

Extensible prime generator (view source)

Revision as of 15:18, 3 December 2023

17,181 bytes added ,  5 months ago
m
Added Easylang
m (Added Easylang)
 
(11 intermediate revisions by 7 users not shown)
Line 172:
The 10,000th prime: 104729</pre>
 
=={{header|BQNBASIC}}==
==={{header|FreeBASIC}}===
This program uses the Sieve Of Eratosthenes which is not very efficient for large primes but is quick enough for present purposes.
 
The size of the sieve array (of type Boolean) is calculated as 20 times the number of primes required which is big enough to compute
up to 50 million primes (a sieve size of 1 billion bytes) which takes under 50 seconds on my i3 @ 2.13 GHz. I've limited the
procedure to this but it should certainly be possible to use a much higher figure without running out of memory.
 
It would also be possible to use a more efficient algorithm to compute the optimal sieve size for smaller numbers of primes but this will suffice for now.
 
<syntaxhighlight lang="freebasic">' FB 1.05.0
 
Enum SieveLimitType
number
between
countBetween
End Enum
 
Sub printPrimes(low As Integer, high As Integer, slt As SieveLimitType)
If high < low OrElse low < 1 Then Return ' too small
If slt <> number AndAlso slt <> between AndAlso slt <> countBetween Then Return
If slt <> number AndAlso (low < 2 OrElse high < 2) Then Return
If slt <> number AndAlso high > 1000000000 Then Return ' too big
If slt = number AndAlso high > 50000000 Then Return ' too big
Dim As Integer n
If slt = number Then
n = 20 * high '' big enough to accomodate 50 million primes to which this procedure is limited
Else
n = high
End If
Dim a(2 To n) As Boolean '' only uses 1 byte per element
For i As Integer = 2 To n : a(i) = True : Next '' set all elements to True to start with
Dim As Integer p = 2, q
' mark non-prime numbers by setting the corresponding array element to False
 
Do
For j As Integer = p * p To n Step p
a(j) = False
Next j
' look for next True element in array after 'p'
q = 0
For j As Integer = p + 1 To Sqr(n)
If a(j) Then
q = j
Exit For
End If
Next j
If q = 0 Then Exit Do
p = q
Loop
 
Select Case As Const slt
Case number
Dim count As Integer = 0
For i As Integer = 2 To n
If a(i) Then
count += 1
If count >= low AndAlso count <= high Then
Print i; " ";
End If
If count = high Then Exit Select
End If
Next
 
Case between
For i As Integer = low To high
If a(i) Then
Print i; " ";
End if
Next
 
Case countBetween
Dim count As Integer = 0
For i As Integer = low To high
If a(i) Then count += 1
Next
Print count;
 
End Select
Print
End Sub
 
Print "The first 20 primes are :"
Print
printPrimes(1, 20, number)
Print
Print "The primes between 100 and 150 are :"
Print
printPrimes(100, 150, between)
Print
Print "The number of primes between 7700 and 8000 is :";
printPrimes(7700, 8000, countBetween)
Print
Print "The 10000th prime is :";
Dim t As Double = timer
printPrimes(10000, 10000, number)
Print "Computed in "; CInt((timer - t) * 1000 + 0.5); " ms"
Print
Print "The 1000000th prime is :";
t = timer
printPrimes(1000000, 1000000, number)
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
Print
Print "The 50000000th prime is :";
t = timer
printPrimes(50000000, 50000000, number)
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
 
{{out}}
<pre>
The first 20 primes are :
 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
 
The primes between 100 and 150 are :
 
101 103 107 109 113 127 131 137 139 149
 
The number of primes between 7700 and 8000 is : 30
 
The 10000th prime is : 104729
Computed in 8 ms
 
The 1000000th prime is : 15485863
Computed in 775 ms
 
The 50000000th prime is : 982451653
Computed in 46703 ms
</pre>
 
=={{header|BQN}}==
This implementation uses a simple segmented sieve similar to the one in [[Sieve of Eratosthenes#BQN|Sieve of Eratosthenes]]. In order to match the task most closely, it returns a generator function (implemented as a closure) that outputs another prime on each call, using an underlying <code>primes</code> array that's extended as necessary. Working with one prime at a time is inefficient in an array language, and the given tasks can be solved more quickly using functions from bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn], which also uses a more complicated and faster underlying sieve.
<syntaxhighlight lang="bqn"># Function that returns a new prime generator
Line 1,213 ⟶ 1,345:
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
See [https://rosettacode.org/wiki/Extensible_prime_generator#Pascal Pascal].
{{libheader|SysUtils,StdCtrls}}
This prime generator is based on a custom Delphi object. The object has a number of features:
 
1. It sieves primes generating an array of flags that tells whether a number is prime or not.
 
2. Using that table it generates another table of just prime numbers.
 
3. The tables can be up 4 billion flags under a 32-bit operating system. However there is also the option to use "Bit-Booleans" which can push the limit up to 32
 
4. Tables are generated fast; 1 million primes takes 9 miliseconds to generate; 100 million primes requires about 2 seconds.
 
5. The tool can be used from just about any prime based task. You can determine if a number is prime by testing the corresponding flag. You can find the nth prime by looking at the nth entry int he prime table. You can count primes between two values by counting flags.
 
 
 
<syntaxhighlight lang="Delphi">
 
{{-------- Declaration for BitBoolean Array ------------------}
 
{Bit boolean - because it stores 8 bools per bytye, it will}
{handle up to 16 gigabyte in a 32 bit programming environment}
 
type TBitBoolArray = class(TObject)
private
FSize: int64;
ByteArray: array of Byte;
function GetValue(Index: int64): boolean;
procedure WriteValue(Index: int64; const Value: boolean);
function GetSize: int64;
procedure SetSize(const Value: int64);
protected
public
property Value[Index: int64]: boolean read GetValue write WriteValue; default;
constructor Create;
property Count: int64 read GetSize write SetSize;
procedure Clear(Value: boolean);
end;
 
 
{------------------------------------------------------------}
{ Implementation for Bitboolean array -----------------------}
{------------------------------------------------------------}
 
{ TBitBoolArray }
 
const BitArray: array [0..7] of byte = ($01, $02, $04, $08, $10, $20, $40, $80);
 
function TBitBoolArray.GetValue(Index: int64): boolean;
begin
{Note: (Index and 7) is faster than (Index mod 8)}
Result:=(ByteArray[Index shr 3] and BitArray[Index and 7])<>0;
end;
 
 
procedure TBitBoolArray.WriteValue(Index: int64; const Value: boolean);
var Inx: int64;
begin
Inx:=Index shr 3;
{Note: (Index and 7) is faster than (Index mod 8)}
if Value then ByteArray[Inx]:=ByteArray[Inx] or BitArray[Index and 7]
else ByteArray[Inx]:=ByteArray[Inx] and not BitArray[Index and 7]
end;
 
 
constructor TBitBoolArray.Create;
begin
SetLength(ByteArray,0);
end;
 
 
function TBitBoolArray.GetSize: int64;
begin
Result:=FSize;
end;
 
 
procedure TBitBoolArray.SetSize(const Value: int64);
var Len: int64;
begin
FSize:=Value;
{Storing 8 items per byte}
Len:=Value div 8;
{We need one more to fill partial bits}
if (Value mod 8)<>0 then Inc(Len);
SetLength(ByteArray,Len);
end;
 
 
procedure TBitBoolArray.Clear(Value: boolean);
var Fill: byte;
begin
if Value then Fill:=$FF else Fill:=0;
FillChar(ByteArray[0],Length(ByteArray),Fill);
end;
 
 
 
 
{========== TPrimeSieve =======================================================}
 
 
{Sieve object the generates and holds prime values}
 
{Enable this flag if you need primes past 2 billion.
The flag signals the code to use bit-booleans arrays
which can contain up to 8 x 4 gigabytes = 32 gig booleans.}
 
// {$define BITBOOL}
 
type TPrimeSieve = class(TObject)
private
{$ifdef BITBOOL}
PrimeArray: TBitBoolArray;
{$else}
PrimeArray: array of boolean;
{$endif}
FArraySize: int64;
FPrimeCount: int64;
function GetPrime(Index: int64): boolean;
procedure Clear;
function GetCount: int64;
procedure BuildPrimeTable;
protected
procedure DoSieve;
property ArraySize: int64 read FArraySize;
public
Primes: TIntegerDynArray;
BitBoolean: boolean;
constructor Create;
destructor Destroy; override;
procedure Intialize(Size: int64);
property Flags[Index: int64]: boolean read GetPrime; default;
function NextPrime(Start: int64): int64;
function PreviousPrime(Start: int64): int64;
property Count: int64 read GetCount;
property PrimeCount: int64 read FPrimeCount;
end;
 
 
 
 
 
 
procedure TPrimeSieve.Clear;
begin
{$ifdef BITBOOL}
PrimeArray.Clear(True);
{$else}
FillChar(PrimeArray[0],Length(PrimeArray),True);
{$endif}
end;
 
 
 
constructor TPrimeSieve.Create;
begin
{$ifdef BITBOOL}
PrimeArray:=TBitBoolArray.Create;
BitBoolean:=True;
{$else}
BitBoolean:=False;
{$endif}
end;
 
 
destructor TPrimeSieve.Destroy;
begin
{$ifdef BITBOOL}
PrimeArray.Free;
{$endif}
inherited;
end;
 
 
 
procedure TPrimeSieve.BuildPrimeTable;
{This builds a table of primes which is}
{easier to use than a table of flags}
var I,Inx: integer;
begin
SetLength(Primes,Self.PrimeCount);
Inx:=0;
for I:=0 to Self.Count-1 do
if Flags[I] then
begin
Primes[Inx]:=I;
Inc(Inx);
end;
end;
 
 
 
procedure TPrimeSieve.DoSieve;
{Load flags with true/false to flag that number is prime}
{Note: does not store even values, because except for 2, all primes are even}
{Starts storing flags at Index=3, so reading/writing routines compensate}
{Uses for-loops for boolean arrays and while-loops for Bit-Booleans arrays}
{$ifdef BITBOOL}
var Offset, I, K: int64;
{$else}
var Offset, I, K: cardinal;
{$endif}
begin
Clear;
{Compensate from primes 1,2 & 3, which aren't stored}
FPrimeCount:=ArraySize+3;
{$ifdef BITBOOL}
I:=0;
while I<ArraySize do
{$else}
for I:=0 to ArraySize-1 do
{$endif}
begin
if PrimeArray[I] then
begin
Offset:= I + I + 3;
K:= I + Offset;
while K <=(ArraySize-1) do
begin
if PrimeArray[K] then Dec(FPrimeCount);
PrimeArray[K]:= False;
K:= K + Offset;
end;
end;
{$ifdef BITBOOL} Inc(I); {$endif}
end;
BuildPrimeTable;
end;
 
 
 
function TPrimeSieve.GetPrime(Index: int64): boolean;
{Get a prime flag from array - compensates}
{ for 0,1,2 and even numbers not being stored}
begin
if Index = 1 then Result:=False
else if Index = 2 then Result:=True
else if (Index and 1)=0 then Result:=false
else Result:=PrimeArray[(Index div 2)-1];
end;
 
 
function TPrimeSieve.NextPrime(Start: int64): int64;
{Get next prime after Start}
begin
Result:=Start+1;
while Result<=((ArraySize-1) * 2) do
begin
if Self.Flags[Result] then break;
Inc(Result);
end;
end;
 
 
 
function TPrimeSieve.PreviousPrime(Start: int64): int64;
{Get Previous prime Before Start}
begin
Result:=Start-1;
while Result>0 do
begin
if Self.Flags[Result] then break;
Dec(Result);
end;
end;
 
 
procedure TPrimeSieve.Intialize(Size: int64);
{Set array size and do Sieve to load flag array with}
begin
FArraySize:=Size div 2;
{$ifdef BITBOOL}
PrimeArray.Count:=FArraySize;
{$else}
SetLength(PrimeArray,FArraySize);
{$endif}
DoSieve;
end;
 
 
 
function TPrimeSieve.GetCount: int64;
begin
Result:=FArraySize * 2;
end;
 
 
{===========================================================}
 
procedure ExtensiblePrimeGenerator(Memo: TMemo);
var I,Cnt: integer;
var Sieve: TPrimeSieve;
var S: string;
begin
Sieve:=TPrimeSieve.Create;
try
{Build a table with 1-million primes}
Sieve.Intialize(1000000);
 
Memo.Lines.Add('Showing the first twenty primes');
S:='';
for I:=0 to 20-1 do
S:=S+' '+IntToStr(Sieve.Primes[I]);
Memo.Lines.Add(S);
Memo.Lines.Add('');
 
Memo.Lines.Add('Showing the primes between 100 and 150.');
S:='';
for I:=100 to 150 do
if Sieve.Flags[I] then S:=S+' '+IntToStr(I);
Memo.Lines.Add(S);
Memo.Lines.Add('');
 
Memo.Lines.Add('Showing the number of primes between 7,700 and 8,000.');
Cnt:=0;
for I:=7700 to 8000 do
if Sieve.Flags[I] then Inc(Cnt);
Memo.Lines.Add('Count = '+IntToStr(Cnt));
Memo.Lines.Add('');
 
Memo.Lines.Add('Showing the 10,000th prime.');
Memo.Lines.Add('10,000th Prime = '+IntToStr(Sieve.Primes[10000-1]));
finally Sieve.Free; end;
end;
 
</syntaxhighlight>
{{out}}
<pre>
Showing the first twenty primes
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
 
Showing the primes between 100 and 150.
101 103 107 109 113 127 131 137 139 149
 
Showing the number of primes between 7,700 and 8,000.
Count = 30
 
Showing the 10,000th prime.
10,000th Prime = 104729
Elapsed Time: 19.853 ms.
 
</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc nprim num .
repeat
i = 2
while i <= sqrt num and num mod i <> 0
i += 1
.
until num mod i <> 0
num += 1
.
return num
.
prim = 2
primcnt = 1
proc nextprim . .
prim = nprim (prim + 1)
primcnt += 1
.
for i to 20
write prim & " "
nextprim
.
print ""
while prim < 100
nextprim
.
while prim <= 150
write prim & " "
nextprim
.
print ""
while prim < 7700
nextprim
.
while prim <= 8000
cnt += 1
nextprim
.
print cnt
while primcnt < 10000
nextprim
.
print prim
while primcnt < 100000
nextprim
.
print prim
</syntaxhighlight>
 
=={{header|EchoLisp}}==
Standard prime functions handle numbers < 2e+9. See [http://www.echolalie.org/echolisp/help.html#prime?] . The '''bigint''' library handles large numbers. See [http://www.echolalie.org/echolisp/help.html#bigint.lib]. The only limitations are time, memory, and browser performances ..
Line 1,967 ⟶ 2,492:
 
The thinning out rather suggests an alternative encoding such as by counting the number of "off" bits until the next "on" bit, but this would produce a variable-length packing so that it would no longer be easy to find the bit associated with a given number by something so simple as <code>R = (NN - SORG)/(2*SBITS)</code> as in NEXTPRIME. A more accomplished data compression system might instead offer a reference to a library containing a table of prime numbers, or even store the code for a programme that will generate the data. File Pbag.for is 23,008 bytes long, and of course contains irrelevant commentary and flabby phrases such as "PARAMETER", "INTEGER", "GRASPPRIMEBAG", ''etc''. As is the modern style, the code file is much larger at 548,923 bytes (containing kilobyte sequences of hex CC and of 00), but both are much smaller than the 134,352,896 bytes of file PrimeSieve.bit.
===Alternative Version using the Sorenson Sieve===
This version is written in largely Fortran-77 style (fixed form, GO TO) It uses the dynamic array algorithm as described in the paper, "Two Compact Incremental Prime Sieves" by Jonathon P. Sorenson. The sieve is limited to an upper bound of 2^31 (in Fortran, integers are always signed) To be correct for that upper limit, signed overflow that can occur for items in the buckets (8 16-bit signed integers) must be taken into account.
 
This code is also written in old style in that the generator uses statically allocated variables to maintain state. It is not re-entrant and there can only be one generator in use at a time. That's more in line with programming practices in the 70s and 80s.
=={{header|FreeBASIC}}==
This program uses the Sieve Of Eratosthenes which is not very efficient for large primes but is quick enough for present purposes.
 
In Fortran, dynamic arrays are always exactly allocated without any over capacity for later expansion, so naively re-allocating the array by 2 as specified in the original paper results in a significant drop in performance due to all of the memory moves. Therefore, this implementation keeps track of the array size which will be less than the array capacity.
The size of the sieve array (of type Boolean) is calculated as 20 times the number of primes required which is big enough to compute
<syntaxhighlight lang="Fortran">
up to 50 million primes (a sieve size of 1 billion bytes) which takes under 50 seconds on my i3 @ 2.13 GHz. I've limited the
* incremental Sieve of Eratosthenes based on the paper,
procedure to this but it should certainly be possible to use a much higher figure without running out of memory.
* "Two Compact Incremental Prime Sieves"
 
SUBROUTINE nextprime(no init, p)
It would also be possible to use a more efficient algorithm to compute the optimal sieve size for smaller numbers of primes but this will suffice for now.
IMPLICIT NONE
INTEGER*2, SAVE, ALLOCATABLE :: sieve(:,:)
INTEGER, SAVE :: r, s, pos, n, f1, f2, sz
INTEGER i, j, d, next, p, f3
LOGICAL no init, is prime
 
IF (no init) GO TO 10
<syntaxhighlight lang="freebasic">' FB 1.05.0
IF (ALLOCATED(sieve)) DEALLOCATE(sieve)
 
* Each row in the sieve is a stack of 8 short integers. The
Enum SieveLimitType
* stacks will never overflow since the product 2*3*5 ... *29
number
* (10 primes) exceeds a 32 bit integer. 2 is not stored in the sieve.
between
countBetween
End Enum
 
ALLOCATE(sieve(8,3))
Sub printPrimes(low As Integer, high As Integer, slt As SieveLimitType)
sieve = reshape([(0_2, i = 1, 24)], shape(sieve))
If high < low OrElse low < 1 Then Return ' too small
r = 3
If slt <> number AndAlso slt <> between AndAlso slt <> countBetween Then Return
s = 9
If slt <> number AndAlso (low < 2 OrElse high < 2) Then Return
pos = 1
If slt <> number AndAlso high > 1000000000 Then Return ' too big
sz = 1 ! sieve starts with size = 1
If slt = number AndAlso high > 50000000 Then Return ' too big
f1 = 2 ! Fibonacci sequence for allocating new capacities
Dim As Integer n
f2 = 3 ! array starts with capacity 3
If slt = number Then
n = 1
n = 20 * high '' big enough to accomodate 50 million primes to which this procedure is limited
p = 2 ! return our first prime
Else
n = highRETURN
End If
Dim a(2 To n) As Boolean '' only uses 1 byte per element
For i As Integer = 2 To n : a(i) = True : Next '' set all elements to True to start with
Dim As Integer p = 2, q
' mark non-prime numbers by setting the corresponding array element to False
 
10 n = n + 2
Do
For j Asis Integerprime = p * p To n Step p.true.
IF (sieve(1, pos) .eq. 0) GO TO 20 ! n is non-smooth w.r.t sieve
a(j) = False
is prime = .false. ! element at sieve(pos) divides n
Next j
' look forDO next17, Truei element= in1, array after 'p'8
q = 0
For j As Integer = p + 1 To Sqr(n)
If a(j) Then
q = j
Exit For
End If
Next j
If q = 0 Then Exit Do
p = q
Loop
 
Clear the stack of divisors by moving them to the next multiple
Select Case As Const slt
Case number
Dim count As Integer = 0
For i As Integer = 2 To n
If a(i) Then
count += 1
If count >= low AndAlso count <= high Then
Print i; " ";
End If
If count = high Then Exit Select
End If
Next
 
d = sieve(i, pos)
Case between
For i AsIF Integer(d =.eq. low0) ToGO highTO 20 ! stack is empty
IfIF a(id .lt. 0) Thend = d + 65536 ! correct storage overflow
sieve(i, pos) Print i; "= ";0
Endnext if= mod(pos + d - 1, sz) + 1
Next
 
* Push divisor d on to the stack of the next multiple
Case countBetween
Dim count As Integer = 0
For i As Integer = low To high
If a(i) Then count += 1
Next
Print count;
 
j = 1
End Select
12 IF (sieve(j, next) .eq. 0) GO TO 15
Print
j = j + 1
End Sub
GO TO 12
15 sieve(j, next) = d
17 CONTINUE
 
Check if n is square; if so, then add sieving prime and advance
Print "The first 20 primes are :"
Print
printPrimes(1, 20, number)
Print
Print "The primes between 100 and 150 are :"
Print
printPrimes(100, 150, between)
Print
Print "The number of primes between 7700 and 8000 is :";
printPrimes(7700, 8000, countBetween)
Print
Print "The 10000th prime is :";
Dim t As Double = timer
printPrimes(10000, 10000, number)
Print "Computed in "; CInt((timer - t) * 1000 + 0.5); " ms"
Print
Print "The 1000000th prime is :";
t = timer
printPrimes(1000000, 1000000, number)
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
Print
Print "The 50000000th prime is :";
t = timer
printPrimes(50000000, 50000000, number)
Print "Computed in ";CInt((timer - t) * 1000 + 0.5); " ms"
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
 
20 IF (n .lt. s) GO TO 30
{{out}}
IF (.not. is prime) GO TO 25
<pre>
is prime = .false. ! r = √s divides n
The first 20 primes are :
next = mod(pos + r - 1, sz) + 1 ! however, r is prime, insert it.
 
j = 1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
22 IF (sieve(j, next) .eq. 0) GO TO 23
j = j + 1
GO TO 22
23 sieve(j, next) = r
 
25 r = r + 2
The primes between 100 and 150 are :
s = r**2
 
Continue to the next array slot; grow the array by two when
101 103 107 109 113 127 131 137 139 149
* we get to the end to maintain the invariant size(sieve) > √n
* IF the size exceeds the array capacity, resize the arary.
 
30 pos = pos + 1
The number of primes between 7700 and 8000 is : 30
IF (pos .le. sz) GO TO 40
sz = sz + 2
pos = 1
 
IF (sz .le. f2) GO TO 40 ! so far, no need to grow
The 10000th prime is : 104729
f3 = f1 + f2
Computed in 8 ms
f1 = f2
f2 = f3
sieve = reshape(sieve, [8, f2],
& pad = [(0_2, i = 1, 8*(f2 - f1))])
 
* Either return n back to the caller or circle back if n
The 1000000th prime is : 15485863
* turned out to be composite.
Computed in 775 ms
 
40 IF (.not. is prime) GO TO 10
p = n
END SUBROUTINE
</syntaxhighlight>
The driver code:
<syntaxhighlight lang="fortran">
INCLUDE 'sieve.f'
 
PROGRAM RC Extensible Sieve
IMPLICIT INTEGER (A-Z)
 
WRITE (*, '(A)', advance='no')
The 50000000th prime is : 982451653
& 'The first 20 primes:'
Computed in 46703 ms
 
CALL nextprime(.false., p)
DO 10, i = 1, 20
WRITE (*, '(I3)', advance = 'no') p
10 CALL nextprime(.true., p)
WRITE (*, *)
 
WRITE (*, '(A)', advance = 'no')
& 'The primes between 100 and 150:'
 
20 CALL nextprime(.true., p)
IF (p .gt. 149) GO TO 30
IF (p .gt. 99)
& WRITE (*, '(I4)', advance = 'no') p
GO TO 20
30 WRITE (*, *)
 
count = 0
40 CALL nextprime(.true., p)
IF (p .gt. 7999) GO TO 50
IF (p .gt. 7700) count = count + 1
GO TO 40
50 WRITE (*, 100) count
100 FORMAT ('There are ', I0, ' primes between 7700 and 8000.')
 
CALL nextprime(.false., p) ! re-initialize
target = 1 ! target count
n = 0 ! number of primes generated
60 n = n + 1
IF (n .lt. target) GO TO 70
WRITE (*, '(ES7.1,1X,I12)'), real(n), p
IF (target .eq. 100 000 000) GO TO 80
target = target * 10
70 CALL nextprime(.true., p)
GO TO 60
 
80 END
</syntaxhighlight>
{{Out}}
<pre>
The first 20 primes: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
The primes between 100 and 150: 101 103 107 109 113 127 131 137 139 149
There are 30 primes between 7700 and 8000.
1.0E+00 2
1.0E+01 29
1.0E+02 541
1.0E+03 7919
1.0E+04 104729
1.0E+05 1299709
1.0E+06 15485863
1.0E+07 179424673
1.0E+08 2038074743
</pre>
 
Line 2,113 ⟶ 2,666:
The 10,000th prime is: 104729
</pre>
 
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn IsPrime( n as NSUInteger ) as BOOL
BOOL isPrime = YES
NSUInteger i
if n < 2 then exit fn = NO
if n = 2 then exit fn = YES
if n mod 2 == 0 then exit fn = NO
for i = 3 to int(n^.5) step 2
if n mod i == 0 then exit fn = NO
next
end fn = isPrime
 
 
local fn ExtensiblePrimes
long c = 0, n = 2, count = 0, track = 0
printf @"The first 20 prime numbers are: "
while ( c < 20 )
if ( fn IsPrime(n) )
printf @"%ld \b", n
c++
end if
n++
wend
printf @"\n\nPrimes between 100 and 150 include: "
for n = 100 to 150
if ( fn IsPrime(n) ) then printf @"%ld \b", n
next
printf @"\n\nPrimes beween 7,700 and 8,000 include: "
c = 0
for n = 7700 to 8000
if ( fn IsPrime(n) ) then c += fn IsPrime(n) : printf @"%ld \b", n : count++ : track++
if count = 10 then print : count = 0
next
printf @"There are %ld primes beween 7,700 and 8,000.", track
printf @"\nThe 10,000th prime is: "
c = 0 : n = 1
while ( c < 10000 )
n++
c += fn IsPrime(n)
wend
printf @"%ld", n
end fn
 
CFTimeInterval t
 
t = fn CACurrentMediaTime
fn ExtensiblePrimes
printf @"\nCompute time: %.3f ms",(fn CACurrentMediaTime-t)*100
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
The first 20 prime numbers are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
 
Primes between 100 and 150 include:
101 103 107 109 113 127 131 137 139 149
 
Primes beween 7,700 and 8,000 include:
7703 7717 7723 7727 7741 7753 7757 7759 7789 7793
7817 7823 7829 7841 7853 7867 7873 7877 7879 7883
7901 7907 7919 7927 7933 7937 7949 7951 7963 7993
There are 30 primes beween 7,700 and 8,000.
 
The 10,000th prime is:
104729
 
Compute time: 73.034 ms
</pre>
 
 
=={{header|Go}}==
Line 3,424 ⟶ 4,055:
As noted in that section, using an extensible generator isn't the best choice for huge ranges as much higher efficiency can be obtained by using functions that deal directly with the composite culled packed-bit array representations directly as the `countPrimesTo` function does. This makes further improvements to the culling efficiency pointless, as even if one were to reduce the culling speed to zero, it still would take several seconds per range of a billion to enumerate the found primes as a generator.
 
=={{header|PARI/GPOCaml}}==
;2-3-5-7-wheel postponed incremental sieve
<syntaxhighlight lang="ocaml">module IntMap = Map.Make(Int)
 
let rec steps =
4 :: 2 :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 6 :: 6 :: 2 ::
6 :: 4 :: 2 :: 6 :: 4 :: 6 :: 8 :: 4 :: 2 :: 4 :: 2 :: 4 ::
8 :: 6 :: 4 :: 6 :: 2 :: 4 :: 6 :: 2 :: 6 :: 6 :: 4 :: 2 ::
4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 2 :: 10 :: 2 :: 10 :: 2 :: steps
 
let not_in_wheel =
let scan i =
let rec loop n w = n < 223 && (i = n mod 210
|| match w with [] -> assert false | d :: w' -> loop (n + d) w')
in not (loop 13 steps)
in Array.init 210 scan
 
let seq_primes =
let rec calc ms m p2 =
if not_in_wheel.(m mod 210) || IntMap.mem m ms
then calc ms (m + p2) p2
else IntMap.add m p2 ms
in
let rec next c p pp ps whl ms () =
match whl with
| [] -> assert false
| d :: w -> match IntMap.min_binding_opt ms with
| Some (m, p2) when c = m ->
next (c + d) p pp ps w (calc (IntMap.remove m ms) (m + p2) p2) ()
| _ when c < pp -> Seq.Cons (c, next (c + d) p pp ps w ms)
| _ -> match ps () with
| Seq.Cons (p', ps') -> let p2' = p + p in
next (c + d) p' (p' * p') ps' w (calc ms (pp + p2') p2') ()
| _ -> assert false
in
let rec ps () = next 13 11 121 ps steps IntMap.empty () in
Seq.cons 2 (Seq.cons 3 (Seq.cons 5 (Seq.cons 7 (Seq.cons 11 ps))))</syntaxhighlight>
;Test code
<syntaxhighlight lang="ocaml">let seq_show sq =
print_newline (Seq.iter (Printf.printf " %u") sq)
 
let () =
seq_primes |> Seq.take 20 |> seq_show;
seq_primes |> Seq.drop_while ((>) 100) |> Seq.take_while ((>) 150) |> seq_show;
seq_primes |> Seq.drop_while ((>) 7700) |> Seq.take_while ((>) 8000)
|> Seq.length |> Printf.printf " %u primes\n";
seq_primes |> Seq.drop 9999 |> Seq.take 1 |> seq_show</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
101 103 107 109 113 127 131 137 139 149
30 primes
104729
</pre>
 
=={{header|PARI/GP}}==
PARI includes a nice prime generator which is quite extensible:
<syntaxhighlight lang="c">void
Line 3,447 ⟶ 4,132:
=={{header|Pascal}}==
{{works with|Free Pascal}}
Limited to 2.7e14. Much faster than the other Version
<b>there is something wrong </b>
<pre >
http://www.primos.mat.br/Ate100G.html ->
75. de 16639648367 a 16875026921
76. de 16875026963 a 17110593779
77. de 17110593791 a 17346308407
...
my unit:
750000000 16875026921
760000000 17110593779
770000000 17346251243 <----Wrong
</pre>
 
Limited to 2.7e14. Much faster than the other Version. 94s to 257 s for the primes 2..1E11
First the unit.Still a work in progress.
 
Line 3,471 ⟶ 4,143:
<syntaxhighlight lang="pascal">
unit primsieve;
//{$O+,R+}
{$IFDEF FPC}
{$MODE objFPC}{$Optimization ON,ALL}
{$CODEALIGN proc=32,loop=1}
{$IFEND}
{segmented sieve of Erathostenes using only odd numbers}
Line 3,484 ⟶ 4,154:
function SieveSize :LongInt;
function Nextprime: Uint64;
function StartCount :Uint64;
function TotalCount :Uint64;
function PosOfPrime: Uint64;
Line 3,511 ⟶ 4,182:
{$ALIGN 32}
//prime = FoundPrimesOffset + 2*FoundPrimes[0..FoundPrimesCnt]
FoundPrimes : array[0..12252cSieveSize] of Wordword;
{$ALIGN 32}
sievePrimes : array[0..78498] of tSievePrim;// 1e6^2 ->1e12
// sievePrimes : array[0..1077863664579] of tSievePrim;// maximum 1e14
FoundPrimesOffset : Uint64;
FoundPrimesCnt,
Line 3,557 ⟶ 4,228:
function InsertSievePrimes(PrimPos:NativeInt):NativeInt;
var
jdelta :NativeUINtNativeInt;
i,pr,loLmt : NativeUInt;
begin
i := 0;
Line 3,565 ⟶ 4,236:
i := maxPreSievePrimeNum;
pr :=0;
jloLmt := Uint64(SieveNum)*cSieveSize*(2-LastInsertedSievePrime*cSieveSize);
delta := loLmt-LastInsertedSievePrime;
with sievePrimes[PrimPos] do
Begin
pr := FoundPrimes[i]*2+1;
svdeltaPrime := pr+jdelta;
jdelta := pr;
end;
 
inc(PrimPos);
for i := i+1 to FoundPrimesCnt-1 do
Line 3,580 ⟶ 4,253:
Begin
pr := FoundPrimes[i]*2+1;
svdeltaPrime := (pr-jdelta);
jdelta := pr;
end;
inc(PrimPos);
end;
LastInsertedSievePrime :=Uint64(SieveNum)*cSieveSize*2 loLmt+pr;
result := PrimPos;
end;
Line 3,636 ⟶ 4,309:
SieveNum :=0;
CopyPreSieveInSieve;
//normal sieving of first block sieve
i := 1; // start with 3
repeat
Line 3,654 ⟶ 4,327:
CollectPrimes;
PrimPos := InsertSievePrimes(0);
//correct for SieveNum = 0
LastInsertedSievePrime := FoundPrimes[PrimPos]*2+1;
CalcSievePrimOfs(PrimPos);
 
Init0Sieve;
sieveOneBlock;
//now start collect with SieveNum = 1
IF PrimPos < High(sievePrimes) then
Begin
Init0Sieve;
//Erste Sieb nochmals, aber ohne Eintrag
sieveOneBlock;
repeat
sieveOneBlock;
CollectPrimes;
dec(SieveNum);
PrimPos := InsertSievePrimes(PrimPos);
inc(SieveNum);
until PrimPos > High(sievePrimes);
end;
Init0Sieve;
end;
Line 3,758 ⟶ 4,430:
procedure CollectPrimes;
//extract primes to FoundPrimes
 
//
var
pSieve : pbyte;
Line 3,764 ⟶ 4,436:
i,idx : NativeUint;
Begin
FoundPrimesOffset := SieveNum*(2*cSieveSize);
FoundPrimesIdx := 0;
pFound :=@FoundPrimes[0];
Line 3,791 ⟶ 4,463:
end;
 
procedure SieveOneBlock;inline;
begin
CopyPreSieveInSieve;
Line 3,799 ⟶ 4,471:
end;
 
procedure NextSieve;inline;
Begin
SieveOneBlock;
Line 3,814 ⟶ 4,486:
end;
 
function PosOfPrime: Uint64;inline;
Begin
result := FoundPrimesTotal-FoundPrimesCnt+FoundPrimesIdx;
end;
 
function TotalCountStartCount : Uint64 ;inline;
begin
result := FoundPrimesTotal-FoundPrimesCnt;
end;
 
function TotalCount :Uint64;inline;
begin
result := FoundPrimesTotal;
end;
 
function SieveSize :LongInt;inline;
Begin
result := 2*cSieveSize;
end;
 
function SieveStart:Uint64;inline;
Begin
result := (SieveNum-1)*2*cSieveSize;
end;
 
procedure InitPrime;inline;
Begin
Init0Sieve;
Line 3,845 ⟶ 4,522:
InitPrime;
end.
</syntaxhighlight>
{compiler: fpc/3.2.0/ppcx64 -Xs -O4 "%f"
50851378 in 1000079360 dauerte 529 ms
455052800 in 10000007168 dauerte 6297 ms
4118057696 in 100000071680 dauerte 93783 ms
}</syntaxhighlight>
 
;the test program:
<syntaxhighlight lang="pascal">
program test;
{$IFDEF FPC}
{$MODE objFPC}{$Optimization ON,ALL}
{$IFEND}
 
uses
primsieve;
 
var
icnt,p,lmt : NativeIntUint64;
cnt : Uint64;
Begin
lmt := 1000*1000*1000;
writeln('First 25 primes');
For ip := 1 to 25 do0;
while TotalCount < lmt do
write(Nextprime:3);
Begin
writeln;
NextSieve;
Writeln;
inc(p);
writeln('Primes betwenn 100 and 150');
If p AND (4096-1) = 0 then
repeat
write(p:8,TotalCount:15,#13);
i := NextPrime
end;
until i > 100;
cnt := StartCount;
repeat
write(i:4);
i := NextPrime;
until i>150;
writeln;
Writeln;
repeat
i := NextPrime
until i > 7700;
cnt := 0;
repeat
p := NextPrime;
inc(cnt);
until cnt i :>= NextPrimelmt;
writeln(cnt:14,p:14);
until i> 8000;
end.
writeln('between 7700 and 8000 are ',cnt,' primes');
{
Writeln;
10^n primecount
writeln(' i.th prime');
# 1 4
cnt := 10000;
# 2 25
repeat
# 3 while TotalCount < cnt do 168
# 4 NextSieve; 1229
# 5 repeat 9592
# 6 i := NextPrime; 78498
# 7 until PosOfPrime = cnt; 664579
# 8 5761455
writeln(cnt:10,i:12);
# 9 cnt := cnt*10; 50847534
# 10 455052511
until cnt >100*1000*1000;
# 11 4118054813
end.</syntaxhighlight>
# 12 37607912018
;output:
}</syntaxhighlight>
<pre>
{{out|@home}}
First 25 primes
<pre>//4.4 Ghz Ryzen 5600G fpc 3.3.1 -O3 -Xs
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
50847534 999999937
 
real 0m0,386s
Primes betwenn 100 and 150
455052511 9999999967
101 103 107 109 113 127 131 137 139 149
real 0m4,702s
 
4118054813 99999999977
between 7700 and 8000 are 30 primes
real 1m11,085s
 
37607912018 999999999989
i.th prime
real 19m1,195s
10000 104729
100000 1299709
1000000 15485863
10000000 179424673
100000000 2038074743
 
real 0m1,121s
</pre>
 
Line 5,975 ⟶ 6,636:
=={{header|Wren}}==
This uses a larger wheel than the sieve in the Wren-math module and is a bit faster if one is sieving beyond about 10^7.
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var primeSieve = Fn.new { |limit|
Chkas
2,041

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/335360...352406"