Extensible prime generator: Difference between revisions
m
Added Easylang
GordonBGood (talk | contribs) m (Extensible Prime Generator page fix highlighting...) |
m (Added Easylang) |
||
| (15 intermediate revisions by 10 users not shown) | |||
Line 38:
The solution uses the package Miller_Rabin from the [[Miller-Rabin primality test]]. When using the gnat Ada compiler, the largest integer we can deal with is 2**63-1. For anything larger, we could use a big-num package.
<syntaxhighlight lang=
procedure Prime_Gen is
Line 120:
=={{header|AutoHotkey}}==
<syntaxhighlight lang=
p := 1 ;p functions as the counter
Loop, 10000 {
Line 172:
The 10,000th prime: 104729</pre>
=={{header|
==={{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
PrimeGen ← {𝕤
i ← 0 # Counter: index of next prime to be output
Line 194 ⟶ 326:
_w_←{𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩} # Looping utility for the session below</syntaxhighlight>
{{out}}
<syntaxhighlight lang="bqn"> pg ← PrimeGen@
(function block)
Line 211 ⟶ 343:
=={{header|C}}==
Extends the list of primes by sieving more chunks of integers. There's no serious optimizations. The code can calculate all 32-bit primes in some seconds, and will overflow beyond that.
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 329 ⟶ 461:
* ~100,000,000 primes is about the limits of this algorithm. This version is not as idiomatic to C as a page-segmented sieve would be.
<syntaxhighlight lang=
#include <stdio.h>
#include <stdlib.h>
Line 468 ⟶ 600:
Based on "The Genuine Sieve of Eratosthenes" by Melissa E. O'Neill.
UPDATE: Added wheel optimization to match its C counterpart.
<syntaxhighlight lang="cpp">#include <iostream>
#include <cstdint>
#include <queue>
Line 609 ⟶ 741:
This is a "segmented sieve" implementation inspired by the original C solution.
Execution time is about 4 seconds on my system (macOS 10.15.4, 3.2GHz Quad-Core Intel Core i5).
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <cmath>
Line 752 ⟶ 884:
=={{header|Clojure}}==
<syntaxhighlight lang=
(:gen-class)
(:require [clojure.string :as string]))
Line 813 ⟶ 945:
The above version is adequate for ranges up to the low millions, so covers the task requirements of primes up to just over a hundred thousands easily. However, it has a O(n^(3/2)) performance which means that it gets slow quite quickly with range as compared to a true incremental Sieve of Eratosthenes, which has O(n (log n)) performance. The following code is about the same speed for ranges in the low millions but quickly passes the above code in speed for large ranges to where it only takes 10's of seconds for a range of a hundred million where the above code takes thousands of seconds. The code is based on the Richard Bird list based Sieve of Eratosthenes mentioned in the O'Neil article but has infinite tree folding added as well as wheel factorization so that it is about the same speed and performance as a Sieve of Eratosthenes based on a priority queue; the code is written here in purely functional form with no mutation, as follows:
<syntaxhighlight lang="clojure">(deftype CIS [v cont]
clojure.lang.ISeq
(first [_] v)
Line 916 ⟶ 1,048:
=={{header|CoffeeScript}}==
This uses the prime number generation algorithm outlined in the paper, "Two Compact Incremental Prime Sieves" by Jonathon P. Sorenson. This algorithm is essentially a rolling segmented SoE, and is quite fast for languages that have good array processing.
<syntaxhighlight lang=
primes = () ->
yield 2
Line 955 ⟶ 1,087:
</syntaxhighlight>
Driver code:
<syntaxhighlight lang=
primes = require('sieve').primes
Line 997 ⟶ 1,129:
=={{header|D}}==
This uses a Prime struct defined in the [[Sieve of Eratosthenes#Extensible Version|third entry of the Sieve of Eratosthenes]] task. Prime keeps and extends a dynamic array instance member of uints. The Prime struct has a opCall that returns the n-th prime number. The opCall calls a grow() private method until the dynamic array of primes is long enough to contain the required answer. The function grow() just grows the dynamic array geometrically and performs a normal sieving. On a 64 bit system this program works up to the maximum prime number that can be represented in the 32 bits of an uint. This program is less efficient than the C entry, so it's better to not use it past some tens of millions of primes, but it's enough for more limited usages.
<syntaxhighlight lang="d">void main() {
import std.stdio, std.range, std.algorithm, sieve_of_eratosthenes3;
Line 1,018 ⟶ 1,150:
===Faster Alternative Version===
<syntaxhighlight lang="d">/// Prime sieve based on: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
import std.container: Array, BinaryHeap, RedBlackTree;
Line 1,142 ⟶ 1,274:
A version based on a (hashed) Map:
<syntaxhighlight lang="dart">Iterable<int> primesMap() {
Iterable<int> oddprms() sync* {
yield(3); yield(5); // need at least 2 for initialization
Line 1,213 ⟶ 1,345:
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{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 ..
<syntaxhighlight lang="lisp">
; the first twenty primes
(primes 20)
Line 1,258 ⟶ 1,783:
The [[Sieve_of_Eratosthenes#Elixir]] Task page lists two "infinite" extensible generators at the bottom. The first of those, using a (hash) Map is reproduced here along with the code to fulfill the required tasks:
<syntaxhighlight lang="elixir">defmodule PrimesSoEMap do
@typep stt :: {integer, integer, integer, Enumerable.integer, %{integer => integer}}
Line 1,344 ⟶ 1,869:
This task uses [http://www.rosettacode.org/wiki/Sieve_of_Eratosthenes#Unbounded_Page-Segmented_Bit-Packed_Odds-Only_Mutable_Array_Sieve Unbounded_Page-Segmented_Bit-Packed Odds-Only Mutable Array Sieve F#]
===The functions===
<syntaxhighlight lang="fsharp">
let primeZ fN =primes()|>Seq.unfold(fun g-> Some(fN(g()), g))
let primesI() =primeZ bigint
Line 1,355 ⟶ 1,880:
===The Task===
<syntaxhighlight lang="fsharp">
Seq.take 20 primes32()|> Seq.iter (fun n-> printf "%d " n)
</syntaxhighlight>
Line 1,362 ⟶ 1,887:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
</pre>
<syntaxhighlight lang="fsharp">
primes32() |> Seq.skipWhile (fun n->n<100) |> Seq.takeWhile (fun n->n<=150) |> Seq.iter (fun n -> printf "%d " n)
</syntaxhighlight>
Line 1,369 ⟶ 1,894:
101 103 107 109 113 127 131 137 139 149
</pre>
<syntaxhighlight lang="fsharp">
printfn "%d" (primes32() |> Seq.skipWhile (fun n->n<7700) |> Seq.takeWhile (fun n->n<=8000) |> Seq.length)
</syntaxhighlight>
Line 1,377 ⟶ 1,902:
</pre>
To demonstrate extensibility I find the 10000th prime.
<syntaxhighlight lang="fsharp">
Seq.item 9999 pCache
</syntaxhighlight>
Line 1,386 ⟶ 1,911:
</pre>
I then find the 10001st prime which takes less time.
<syntaxhighlight lang="fsharp">
Seq.item 10000 pCache
</syntaxhighlight>
Line 1,395 ⟶ 1,920:
</pre>
To indiccate speed I time the following:
<syntaxhighlight lang="fsharp">
let strt = System.DateTime.Now.Ticks
for i = 1 to 8 do
Line 1,415 ⟶ 1,940:
All of the last took 7937 milliseconds.
</pre>
<syntaxhighlight lang="fsharp">printfn "The first 20 primes are: %s"
( primesSeq() |> Seq.take 20
|> Seq.fold (fun s p -> s + string p + " ") "" )
Line 1,451 ⟶ 1,976:
Factor's <code>fixnums</code> automatically promote to <code>bignums</code> when large enough, so there are no limits to its prime generator other than the capabilities of the machine it's running on.
<syntaxhighlight lang="factor">USING: io math.primes prettyprint sequences ;
"First 20 primes: " write
Line 1,498 ⟶ 2,023:
The variables are all the default thirty-two bit two's complement integers and integer overflow is a possibility, especially because someone is sure to wonder what is the largest prime that can be represented in thirty-two bits - see the output. The code would be extensible in another way, if all appearances of <code>INTEGER</code> were to be replaced by <code>INTEGER*8</code> though not all variables need be changed - such as <code>C</code> and <code>B</code> because they need only index a character in array SCHARS or a bit in a character. Using sixty-four bits for such variables is excessive even if the cpu uses a 64-bit data bus to memory. If such a change were to be made, then all would go well as cpu time and disc space were consumed up to the point when the count of prime numbers can no longer be fitted into the four character storage allowance in the record format. This will be when more than 4,294,967,295 primes have been counted (with 64-bit arithmetic its four bytes will manifest as an unsigned integer) in previous records, and Prime(4,294,967,295) = 104,484,802,043, so that the bit file would require a mere 6,530MB or so - which some may think is not too much. If so, expanding the allowance from four to five characters would be easy enough, and then 256 times as many primes could be counted. That would also expand the reach of the record counter, which otherwise would be limited to 4,294,967,295 records of 4096 bytes each, or a bit bag of 17,592,186,040,320 bytes - only seventeen terabytes...
Overflow is also a problem in many of the calculations. For instance, for a given (prime) number F, the marking of multiples of F via the sieve process starts with the bit corresponding to F² and if this exceeds the number corresponding to the last bit of the current sieve span, then the sieve process is complete for this span because all later values for F will be still further past the end. So, if <code>LST</code> is the number corresponding to the last bit of the current span, <syntaxhighlight lang=
DO WHILE(F <= LST/F) !Except, LST might also overflow the integer limit, so
DO WHILE(F <= (IST + 2*(SBITS - 1))/F) !Which becomes...
Line 1,513 ⟶ 2,038:
Although recursion is now permissible if one utters the magic word <code>RECURSIVE</code>, this ability usually is not extended to the workings for formatted I/O so that if say a function is invoked in a WRITE statement's list, should that function attempt to use a WRITE statement, the run will be stopped. There can be slight dispensations if different types of WRITE statement are involved (say, formatted for one, and "free"-format for the other) but an ugly message is the likely result. The various functions are thus best invoked via an assignment statement to a scratch variable, which can then be printed. The functions are definitely not "pure" because although they are indeed functions only of their arguments, they all mess with shared storage, can produce error messages (and even a STOP), and can provoke I/O with a disc file, even creating such a file. For this reason, it would be unwise to attempt to invoke them via any sort of parallel processing. Similarly, the disc file is opened with exclusive use because of the possibility of writing to it. There are no facilities in standard Fortran to control the locking and unlocking of records of a disc file as would be needed when adding a new record and updating the record count. This would be needed if separate tasks could be accessing the bit file at the same time, and is prevented by exclusive use. If an interactive system were prepared to respond to requests for ISPRIME(n), ''etc.'' it should open the bit file only for its query then close it before waiting for the next request - which might be many milliseconds away.
The bit array is stored in an array of type CHARACTER*1 since this has been available longer and more widely than INTEGER*1. One hopes that the consequent genuflections to type checking via functions CHAR(i) and ICHAR(c) will not involve an overhead. <syntaxhighlight lang=
C Creates and expands a disc file for a sieve of Eratoshenes, representing odd numbers only and starting with three.
C Storage requirements: an array of N prime numbers in 16/32/64 bits vs. a bit array up to the 16/32/64 bit limit.
Line 1,911 ⟶ 2,436:
END !Whee!</syntaxhighlight>
Although the structuralist talk up the merit of "structured" constructs in programming, there are often annoying obstacles. With a WHILE-loop one usually has to repeat the "next item" code to "prime" the loop, as in <syntaxhighlight lang=
DO WHILE (P.LE.150)
...stuff...
P = NEXTPRIME(P)
END DO</syntaxhighlight>
While this is not a large imposition in this example, if Fortran were to allow assignment within expressions as in Algol, the tedium of code replication and its risks could be avoided. <syntaxhighlight lang="algol68"> P:=100; WHILE (P:=NextPrime(P)) <= 150 DO stuff;</syntaxhighlight> If instead of NEXTPRIME the "next item" code was to read a record of a disc file, the repetition needed becomes tiresome. So, an IF-statement, and ... a GO TO...
===The Results===
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.
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.
<syntaxhighlight lang="Fortran">
* incremental Sieve of Eratosthenes based on the paper,
* "Two Compact Incremental Prime Sieves"
SUBROUTINE nextprime(no init, p)
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
IF (ALLOCATED(sieve)) DEALLOCATE(sieve)
* Each row in the sieve is a stack of 8 short integers. The
* stacks will never overflow since the product 2*3*5 ... *29
* (10 primes) exceeds a 32 bit integer. 2 is not stored in the sieve.
ALLOCATE(sieve(8,3))
sieve = reshape([(0_2, i = 1, 24)], shape(sieve))
r = 3
s = 9
pos = 1
sz = 1 ! sieve starts with size = 1
f1 = 2 ! Fibonacci sequence for allocating new capacities
f2 = 3 ! array starts with capacity 3
n = 1
p = 2 ! return our first prime
10 n = n + 2
IF (sieve(1, pos) .eq. 0) GO TO 20 ! n is non-smooth w.r.t sieve
is prime = .false. ! element at sieve(pos) divides n
Clear the stack of divisors by moving them to the next multiple
d = sieve(i, pos)
sieve(i, pos)
* Push divisor d on to the stack of the next multiple
j = 1
12 IF (sieve(j, next) .eq. 0) GO TO 15
j = j + 1
GO TO 12
15 sieve(j, next) = d
17 CONTINUE
Check if n is square; if so, then add sieving prime and advance
20 IF (n .lt. s) GO TO 30
IF (.not. is prime) GO TO 25
is prime = .false. ! r = √s divides n
next = mod(pos + r - 1, sz) + 1 ! however, r is prime, insert it.
j = 1
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
s = r**2
Continue to the next array slot; grow the array by two when
* 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
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
f3 = f1 + f2
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
* turned out to be composite.
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 first 20 primes:'
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>
=={{header|Frink}}==
Frink has built-in functions for efficiently enumerating through prime numbers, including <CODE>primes</CODE>, <CODE>nextPrime</CODE>, and <CODE>previousPrime</CODE>, and <CODE>isPrime</CODE>. These functions handle arbitrarily-large integers.
<syntaxhighlight lang="frink">println["The first 20 primes are: " + first[primes[], 20]]
println["The primes between 100 and 150 are: " + primes[100,150]]
println["The number of primes between 7700 and 8000 are: " + length[primes[7700,8000]]]
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}}==
An implementation of "The Genuine Sieve of Eratosthenese" by Melissa E. O'Niell. This is the paper cited above in the "Faster Alternative Version" of D. The Go example here though strips away optimizations such as a wheel to show the central idea of storing prime multiples in a queue data structure.
<syntaxhighlight lang="go">package main
import (
Line 2,214 ⟶ 2,845:
Due to how Go's imports work, the bellow can be given directly to "<code>go run</code>" or "<code>go build</code>" and the latest version of the primegen package will be fetched and built if it's not already present on the system.
(This example may not be exactly within the scope of this task, but it's a trivial to use and extremely fast prime generator probably worth considering whenever primes are needed in Go.)
<syntaxhighlight lang="go">package main
import (
Line 2,250 ⟶ 2,881:
This program uses the [http://hackage.haskell.org/package/primes primes] package, which uses a lazy wheel sieve to produce an infinite list of primes.
<syntaxhighlight lang="haskell">#!/usr/bin/env runghc
import Data.List
Line 2,288 ⟶ 2,919:
Using list based unbounded sieve from [[Sieve_of_Eratosthenes#With_Wheel|here]] (runs instantly):
<syntaxhighlight lang="haskell"> λ> take 20 primesW
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
Line 2,312 ⟶ 2,943:
Haskell have [https://hackage.haskell.org/package/exact-real-0.12.5.1/docs/Data-CReal.html a library of constructive real numbers], where real numbers can be of an arbitrary precision. We can define this constant ''C'' '''exactly''' and use the above formula to calculate the ''n''th prime. This is not the fastest method, but one of the coolest. And it is not as bad as you may think. It took about 0.3 seconds to calculate 10,000th prime using this formula.
<syntaxhighlight lang="haskell">
{-# LANGUAGE PostfixOperators #-}
{-# LANGUAGE DataKinds #-}
Line 2,383 ⟶ 3,014:
Then you can use this function:
<syntaxhighlight lang="haskell">
λ> :set +s
λ> prime 10000
Line 2,404 ⟶ 3,035:
The expression:
<syntaxhighlight lang="unicon">![2,3,5,7] | (nc := 11) | (nc +:= |wheel2345)</syntaxhighlight>
is an open-ended sequence generating potential primes.
<syntaxhighlight lang="unicon">import Collections # to get the Heap class for use as a Priority Queue
record filter(composite, prime) # next composite involving this prime
Line 2,460 ⟶ 3,091:
Using the p: builtin, http://www.jsoftware.com/help/dictionary/dpco.htm reports "Currently, arguments larger than 2^31 are tested to be prime according to a probabilistic algorithm (Miller-Rabin)".
<syntaxhighlight lang=
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
(#~ >:&100)i.&.(p:inv) 150
Line 2,473 ⟶ 3,104:
Note: 4&p: gives the next prime
<syntaxhighlight lang=
104743</syntaxhighlight>
=={{header|Java}}==
Based on my second C++ solution, which in turn was based on the C solution.
<syntaxhighlight lang="java">import java.util.*;
public class PrimeGenerator {
Line 2,619 ⟶ 3,250:
Sounds a bit weird, but I hope it will be intelligible by the testing examples below. First the code:
<syntaxhighlight lang=
var i,
arr = [];
Line 2,662 ⟶ 3,293:
'''Test'''
<syntaxhighlight lang="text">// first 20 primes
console.log(primeGenerator(20, true));
Line 2,675 ⟶ 3,306:
'''Output'''
<syntaxhighlight lang="text">Array [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 59, 61, 67, 71 ]
Array [ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 ]
Line 2,695 ⟶ 3,326:
'''Preliminaries:'''
<syntaxhighlight lang="jq"># Recent versions of jq include the following definition:
# until/2 loops until cond is satisfied,
# and emits the value satisfying the condition:
Line 2,706 ⟶ 3,337:
'''Prime numbers:'''
<syntaxhighlight lang="jq"># Is the input integer a prime?
# "previous" must be the array of sorted primes greater than 1 up to (.|sqrt)
def is_prime(previous):
Line 2,741 ⟶ 3,372:
'''The tasks:'''
The tasks are completed separately here to highlight the fact that by using "extend_primes", each task can be readily completed without generating unnecessarily many primes.
<syntaxhighlight lang="jq">"First 20 primes:", (20 | primes), "",
"Primes between 100 and 150:",
Line 2,751 ⟶ 3,382:
| "There are \($length) primes twixt 7700 and 8000.")</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh">$ jq -r -c -n -f Extensible_prime_generator.jq
First 20 primes:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
Line 2,768 ⟶ 3,399:
and by default determines primes with Knuth's recommended level for cryptography of an error less than
(0.25)^25 = 8.881784197001252e-16, or 1 in 1125899906842624.
<syntaxhighlight lang="julia">using Primes
sum = 2
Line 2,801 ⟶ 3,432:
The above code just uses the "Primes" package as a set of tools to solve the tasks. The following code creates a very simple generator using `isprime` inside a iterator and then uses that to solve the tasks:
<syntaxhighlight lang="julia">using Primes: isprime
PrimesGen() = Iterators.filter(isprime, Iterators.countfrom(Int64(2)))
Line 2,830 ⟶ 3,461:
To show it's speed, lets use it to solve the Euler Problem 10 of calculating the sum of the primes to two million as follows:
<syntaxhighlight lang="julia">using Printf: @printf
@time let sm = 0
for p in Iterators.filter(isprime, Iterators.countfrom(UInt64(2)))
Line 2,849 ⟶ 3,480:
The above code is more than adequate to solve the trivial tasks as required here, but is really too slow for "industrial strength" tasks for ranges of billions. The following code uses the Page Segmented Algorithm from [[Sieve_of_Eratosthenes#Julia]] to solve the task:
<syntaxhighlight lang="julia">using Printf: @printf
print("Sum of first 100,000 primes: ")
Line 2,869 ⟶ 3,500:
To show how much faster it is, doing the same Euler Problem 10 as follows:
<syntaxhighlight lang="julia">using Printf: @printf
@time let sm = 0
for p in PrimesPaged()
Line 2,888 ⟶ 3,519:
Although we could use the java.math.BigInteger type to generate arbitrarily large primes, there is no need to do so here as the primes to be generated are well within the limits of the 4-byte Int type.
((workwith|Kotlin|version 1.3}}
<syntaxhighlight lang="scala">fun isPrime(n: Int) : Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
Line 2,932 ⟶ 3,563:
The following odds-only incremental Sieve of Eratosthenes generator has O(n log (log n)) performance due to using a (mutable) HashMap:
<syntaxhighlight lang="scala">fun primesHM(): Sequence<Int> = sequence {
yield(2)
fun oddprms(): Sequence<Int> = sequence {
Line 2,973 ⟶ 3,604:
It can count the primes to one billion in about 15 seconds on a slow tablet CPU (Intel x5-Z8350 at 1.92 Gigahertz) with the following code:
<syntaxhighlight lang="kotlin">primesPaged().takeWhile { it <= 1_000_000_000 }.count()</syntaxhighlight>
Further speed-ups can be achieved of about a factor of four with maximum wheel factorization and by multi-threading by the factor of the effective number of cores used, but there is little point when most of the execution time as a generator is spend iterating over the results.
Line 2,981 ⟶ 3,612:
=={{header|Lua}}==
The modest requirements of this task allow for naive implementations, such as what follows. This generator does not even use its own list of primes to help determine subsequent primes! (though easily fixed) So, it it sufficient, but not efficient.
<syntaxhighlight lang="lua">local primegen = {
count_limit = 2,
value_limit = 3,
Line 3,045 ⟶ 3,676:
The following script implements a Sieve of Eratosthenes that is automatically extended when a method call needs a higher upper limit.
<syntaxhighlight lang=
property _sieve
Line 3,151 ⟶ 3,782:
end</syntaxhighlight>
<syntaxhighlight lang=
put "First twenty primes: " & sieve.getNPrimes(20)
put "Primes between 100 and 150: "& sieve.getPrimesInRange(100, 150)
Line 3,180 ⟶ 3,811:
Loop statement check a flag in a block of code ({ }), so when the block ends restart again (resetting the loop flag)
<syntaxhighlight lang=
Module CheckPrimes {
\\ Inventories are lists, Known and Known1 are pointers to Inventories
Line 3,301 ⟶ 3,932:
I use same indentation so you can copy it at same position as in example above. A loop statement mark once the current block for restart after then last statement on block.
<syntaxhighlight lang=
PrimeNth=lambda Known, Known1 (n as long) -> {
if n<1 then Error "Only >=1"
Line 3,330 ⟶ 3,961:
Prime and PrimePi use sparse caching and sieving. For large values, the Lagarias–Miller–Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime.
PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.
<syntaxhighlight lang=
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71}
Select[Range[100,150], PrimeQ]
Line 3,342 ⟶ 3,973:
For such trivial ranges as the task requirements or solving the Euler Problem 10 of summing the primes to two million, a basic generator such as the hash table based version from the [[Sieve_of_Eratosthenes#Nim_Unbounded_Versions]] section of the Sieve of Eratosthenes task will suffice, as follows:
<syntaxhighlight lang="nim">import tables
type PrimeType = int
Line 3,416 ⟶ 4,047:
To use that sieve, just substitute the following in the code:
<syntaxhighlight lang="nim">for p in primesPaged():</syntaxhighlight>
wherever the following is in the code:
<syntaxhighlight lang="nim">for p in iter():</syntaxhighlight>
and one doesn't need the lines including `iter` just above these lines at all.
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|
;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
showprimes(GEN lower, GEN upper)
{
Line 3,439 ⟶ 4,124:
Most of these functions are already built into GP:
<syntaxhighlight lang="parigp">primes(20)
primes([100,150])
#primes([7700,8000]) /* or */
Line 3,447 ⟶ 4,132:
=={{header|Pascal}}==
{{works with|Free Pascal}}
Limited to 2.7e14. Much faster than the other Version
First the unit.Still a work in progress.
Line 3,469 ⟶ 4,141:
./primesieve -t1 100000071680 Sieve size = 256 KiB Threads = 1 100%
Seconds: 19.891 Primes: 4118057696
<syntaxhighlight lang="pascal">
unit primsieve;
{$IFDEF FPC}
{$MODE objFPC}{$Optimization ON,ALL}
{$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..
{$ALIGN 32}
sievePrimes : array[0..78498] of tSievePrim;// 1e6^2 ->1e12
// sievePrimes : array[0..
FoundPrimesOffset : Uint64;
FoundPrimesCnt,
Line 3,557 ⟶ 4,228:
function InsertSievePrimes(PrimPos:NativeInt):NativeInt;
var
i,pr,loLmt : NativeUInt;
begin
i := 0;
Line 3,565 ⟶ 4,236:
i := maxPreSievePrimeNum;
pr :=0;
delta := loLmt-LastInsertedSievePrime;
with sievePrimes[PrimPos] do
Begin
pr := FoundPrimes[i]*2+1;
svdeltaPrime := 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-
end;
inc(PrimPos);
end;
LastInsertedSievePrime :=
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
CalcSievePrimOfs(PrimPos);
Init0Sieve;
sieveOneBlock;
//now start collect with SieveNum = 1
IF PrimPos < High(sievePrimes) then
repeat
sieveOneBlock;
CollectPrimes;
dec(SieveNum);
PrimPos := InsertSievePrimes(PrimPos);
inc(SieveNum);
until PrimPos > High(sievePrimes);
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
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>
;the test program:
<syntaxhighlight lang="pascal">
program test;
{$IFDEF FPC}
{$MODE objFPC}{$Optimization ON,ALL}
{$IFEND}
uses
primsieve;
var
Begin
lmt := 1000*1000*1000;
while TotalCount < lmt do
Begin
NextSieve;
inc(p);
If p AND (4096-1) = 0 then
write(p:8,TotalCount:15,#13);
end;
cnt := StartCount;
repeat
p := NextPrime;
inc(cnt);
until cnt
writeln(cnt:14,p:14);
end.
{
10^n primecount
# 1 4
# 2 25
# 3
# 4
# 5
# 6
# 7
# 8 5761455
# 9
# 10 455052511
# 11 4118054813
# 12 37607912018
}</syntaxhighlight>
{{out|@home}}
<pre>//4.4 Ghz Ryzen 5600G fpc 3.3.1 -O3 -Xs
50847534 999999937
real 0m0,386s
455052511 9999999967
real 0m4,702s
4118054813 99999999977
real 1m11,085s
37607912018 999999999989
real 19m1,195s
</pre>
Line 3,924 ⟶ 4,585:
But i can hold all primes til 1e11 in 2.5 Gb memory.Test for isEmirp inserted.
32-bit is slow doing 64-Bit math.Using a dynamic array is slow too in NextPrime.
<syntaxhighlight lang="pascal">program emirp;
{$IFDEF FPC}
{$MODE DELPHI}
Line 4,625 ⟶ 5,286:
* <tt>primes</tt>, <tt>next_prime</tt>, <tt>prev_prime</tt>, <tt>forprimes</tt>, <tt>prime_iterator</tt>, <tt>prime_iterator_object</tt>, and primality tests will work for practically any size input. The [https://metacpan.org/pod/Math::Prime::Util::GMP Math::Prime::Uti::GMP] module is recommended for large inputs. With that module, these functions will work quickly for multi-thousand digit numbers.
<syntaxhighlight lang="perl">use Math::Prime::Util qw(nth_prime prime_count primes);
# Direct solutions.
# primes([start],end) returns an array reference with all primes in the range
Line 4,648 ⟶ 5,309:
There are many other ways, including <tt>prev_prime</tt> / <tt>next_prime</tt>, a simple iterator, an OO style iterator, a tied array, and a Pari-like <tt>forprimes</tt> construct. For example, the above example using the OO iterator:
<syntaxhighlight lang="perl">use Math::Prime::Util "prime_iterator_object";
my $it = prime_iterator_object;
say "First 20: ", join(" ", map { $it->iterate() } 1..20);
Line 4,661 ⟶ 5,322:
say "${_}th prime: ", $it->ith($_) for map { 10**$_ } 1..8;</syntaxhighlight>
Or using forprimes and a tied array:
<syntaxhighlight lang="perl">use Math::Prime::Util qw/forprimes/;
use Math::Prime::Util::PrimeArray;
tie my @primes, 'Math::Prime::Util::PrimeArray';
Line 4,676 ⟶ 5,337:
Example showing bigints:
<syntaxhighlight lang="perl">use bigint;
use Math::Prime::Util qw/forprimes prime_get_config/;
warn "No GMP, expect slow results\n" unless prime_get_config->{gmp};
Line 4,703 ⟶ 5,364:
Some further discussion of this can be found on my talk page --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]])
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">free_console</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
Line 4,786 ⟶ 5,447:
Using the builtins, for comparison only, output is identical though there is a marginal improvement in performance <small>(for reasons lost in the mists of time!)</small>:
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
Line 4,803 ⟶ 5,464:
=={{header|PicoLisp}}==
<syntaxhighlight lang=
(let S (sqrt N)
(for D Lst
Line 4,852 ⟶ 5,513:
===Faster version using a priority queue sieve and 2357 wheel===
This version runs about twice as quickly by using the method above to find small primes as a base for populating the priority queues required for the lazy sieve of Eratosthenes algorithm by Melissa O'Neil.
<syntaxhighlight lang=
(load "plcommon/pairing-heap.l") # Pairing heap from RC task "Priority Queue"
Line 4,922 ⟶ 5,583:
</syntaxhighlight>
Driver code:
<syntaxhighlight lang=
(prin "The first 20 primes: ")
(do 20 (printsp (primes T)))
Line 4,967 ⟶ 5,628:
=={{header|PureBasic}}==
<syntaxhighlight lang=
DisableDebugger
Define StartTime.i=ElapsedMilliseconds()
Line 5,031 ⟶ 5,692:
===Python: Croft spiral===
The Croft spiral sieve prime generator from the [[Prime_decomposition#Python:_Using_Croft_Spiral_sieve|Prime decomposition]] task is used which contains the line <syntaxhighlight lang="python">islice(count(7), 0, None, 2)</syntaxhighlight>
The call to <code>count(7)</code> is to a generator of integers that counts from 7 upwards with no upper limit set.<br>
The definition <code>croft</code> is a generator of primes and is used to generate as many primes as are asked for, in order.
<syntaxhighlight lang="python">from __future__ import print_function
from prime_decomposition import primes
from itertools import islice
Line 5,065 ⟶ 5,726:
With more contemporary itertools use, 210-wheel incremental sieve with postponed primes processing and thus with radically reduced memory footprint which increases slower than square root of the number of primes produced:
<syntaxhighlight lang="python">def wsieve(): # ideone.com/mqO25A
wh11 = [ 2,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 ]
Line 5,114 ⟶ 5,775:
After a [[https://paddy3118.blogspot.com/2018/11/to-infinity-beyond.html?showComment=1541671062388#c8979782377032256564 blog entry]] on implementing a particular Haskell solution in Python.
<syntaxhighlight lang="python">from itertools import count, takewhile, islice
def prime_sieve():
Line 5,162 ⟶ 5,823:
The link referenced in the source: [http://docs.racket-lang.org/math/number-theory.html?q=prime%3F#%28part._primes%29 <code>math/number-theory</code> module documentation]
<syntaxhighlight lang="scheme">#lang racket
;; Using the prime functions from:
(require math/number-theory)
Line 5,212 ⟶ 5,873:
Build a lazy infinite list of primes using the Raku builtin is-prime method. ( A lazy list will not bother to calculate the values until they are actually used. ) That is the first line. If you choose to calculate the entire list, it is fairly certain that you will run out of process / system memory before you finish... (patience too probably) but there aren't really any other constraints. The is-prime builtin uses a Miller-Rabin primality test with 100 iterations, so while it is not 100% absolutely guaranteed that every number it flags as prime actually is, the chances that it is wrong are about 4<sup>-100</sup>. Much less than the chance that a cosmic ray will cause an error in your computers CPU. Everything after the first line is just display code for the various task requirements.
<syntaxhighlight lang=
say "The first twenty primes:\n ", "[{@primes[^20].fmt("%d", ', ')}]";
Line 5,233 ⟶ 5,894:
=={{header|Red}}==
<syntaxhighlight lang=
Red [Description: "Prime checker/generator/counter"]
Line 5,346 ⟶ 6,007:
This REXX program uses some hardcoded divisions. While the hardcoded divisions are not necessary, they do speed up the division process in validating if a number is prime (or not), and the hardcoded divisions bypass the repetitive tests to see if a (low) prime that is being used for division is greater than the number being divided (tested). The hardcoded divisions also bypass (or, at least, postpones) the computation of the integer square roots.
<syntaxhighlight lang="rexx">/*REXX program calculates and displays primes using an extendible prime number generator*/
parse arg f .; if f=='' then f= 20 /*allow specifying number for 1 ──► F.*/
_i= ' (inclusive) '; _b= 'between '; _tnp= 'the number of primes' _b; _tn= 'the primes'
Line 5,408 ⟶ 6,069:
=={{header|Ring}}==
<syntaxhighlight lang="ring">
see "first twenty primes : "
i = 1
Line 5,458 ⟶ 6,119:
=={{header|Ruby}}==
The prime library behaves like an enumerator. It has an "each" method, which takes an upper bound as argument. This argument is nil by default, which means no upper bound.
<syntaxhighlight lang="ruby">require "prime"
puts Prime.take(20).join(", ")
Line 5,476 ⟶ 6,137:
Uses the code from [[Sieve_of_Eratosthenes#Unbounded_Page-Segmented_bit-packed_odds-only_version_with_Iterator]]; copy that code into a file named <code>src/pagesieve.rs</code> and prepend <code>pub</code> to all function declarations used in this code (<code>count_primes_paged</code> and <code>primes_paged</code>).
<syntaxhighlight lang="rust">mod pagesieve;
use pagesieve::{count_primes_paged, primes_paged};
Line 5,506 ⟶ 6,167:
cannot be used, because it needs a limit. Instead the function getPrime is used.
GetPrime generates all primes in sequence.
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
Line 5,580 ⟶ 6,241:
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">say ("First 20: ", 20.nth_prime.primes.join(' '))
say ("Between 100 and 150: ", primes(100,150).join(' '))
say (prime_count(7700,8000), " primes between 7700 and 8000")
Line 5,595 ⟶ 6,256:
The [[Sieve_of_Eratosthenes#Unbounded_.28Odds-Only.29_Versions]] Swift examples contain several versions that are Extensible Prime Generators using the Sieve of Eratosthenese. One of the simplest is the Hashed Dictionary, reproduced here as follows:
<syntaxhighlight lang="swift">import Foundation
func soeDictOdds() -> UnfoldSequence<Int, Int> {
Line 5,666 ⟶ 6,327:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<syntaxhighlight lang="tcl">package require Tcl 8.6
# An iterative version of the Sieve of Eratosthenes.
Line 5,729 ⟶ 6,390:
=={{header|VBA}}==
<syntaxhighlight lang="vb">Option Explicit
Sub Main()
Line 5,818 ⟶ 6,479:
The last prime I could find is the : 7 550 283th, Value : 133 218 289</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
'uses variant booleans for the sieve, so 16 bytes per bit, a little wasteful!
Option Explicit
Sub sieveit(maxi) 'increases sieve size up to maxi and sieves the added part
Dim lasttop,a,b,c,i,j
lasttop=UBound(primes)
If maxi>lasttop Then
ReDim preserve primes(maxi)
print vbcrlf &"(sieving from " & lasttop & " up to " & maxi &")"& vbCrLf
For i=lasttop+1 To maxi
primes(i)=True
next
For i=2 To Int(Sqr(lasttop))
If primes(i)=True Then
a=lasttop\i
b=maxi\i
c= i*a
For j=a To b
primes(c)=False
c=c+i
Next
End if
Next
For i=Int(Sqr(lasttop)) To Int(Sqr(maxi))
If primes(i)=True Then
c=i*i
While c<=maxi
primes(c)=False
c=c+i
wend
End if
next
End if
End Sub
function nth(n) 'returns the nth prime (sieves if needed)
Dim cnt,i,m
m=Int(n *(Log(n)+Log(Log(n))))
If m>UBound(primes) Then sieveit (m)
i=1
Do
i=i+1
If primes(i) Then cnt=cnt+1
Loop until cnt=n
nth=i
End function
Sub printprimes (x1, x2,p) ' counts and prints (if p=true) primes between x1 and x2 (sieves if needed)
Dim lasttop,n,cnt,i
If x2> UBound(primes) Then sieveit(x2)
print "primes in range " & x1 & " To " & x2 & vbCrLf
cnt=0
For i=x1 To x2
If primes(i) Then
If p Then print i & vbTab
cnt=cnt+1
End if
next
print vbCrLf & "Count: " & cnt
End Sub
Sub print(s):
On Error Resume Next
WScript.stdout.WriteLine (s)
If err= &h80070006& Then WScript.Echo " Please run this script with CScript": WScript.quit
End Sub
' main program-------------------------------------------
Dim n
' initialization of the array of booleans
reDim Primes(2)
primes(0) = False
Primes(1) = False
Primes(2) = True
'Show the first twenty primes.
n=nth(20)
printprimes 1,n,1
'Show the primes between 100 and 150.
printprimes 100,150,1
'Show the number of primes between 7,700 and 8,000.
printprimes 7700,8000,0
'Show the 10,000th prime.
n= nth(10000)
print n & " is the " & 10000 & "th prime"
</syntaxhighlight>
{{out}}
<small>
<pre>
(sieving from 2 up to 81)
primes in range 1 To 71
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
Count: 20
(sieving from 81 up to 150)
primes in range 100 To 150
101
103
107
109
113
127
131
137
139
149
Count: 10
(sieving from 150 up to 8000)
primes in range 7700 To 8000
Count: 30
(sieving from 8000 up to 114306)
104729 is the 10000th prime
</pre>
</small>
=={{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=
var primeSieve = Fn.new { |limit|
Line 5,904 ⟶ 6,720:
Implementation:
<syntaxhighlight lang=
const std = @import("std");
const builtin = std.builtin;
Line 6,059 ⟶ 6,875:
</syntaxhighlight>
Driver code:
<syntaxhighlight lang=
const std = @import("std");
const sieve = @import("sieve.zig");
Line 6,150 ⟶ 6,966:
Since this version uses an array (O(1)) rather than an O(log n) priority queue, it is significantly faster. On my laptop, sieving up to 100,000,000 primes takes 2:18 seconds for the O'Neil sieve and 52 seconds for the Sorenson.
<syntaxhighlight lang=
// Since in the common case (primes < 2^32 - 1), the stack only needs to be 8 16-bit words long
// (only twice the size of a pointer) the required stacks are stored in each cell, rather
Line 6,359 ⟶ 7,175:
=={{header|zkl}}==
<syntaxhighlight lang="zkl">// http://stackoverflow.com/revisions/10733621/4
fcn postponed_sieve(){ # postponed sieve, by Will Ness
Line 6,389 ⟶ 7,205:
D[x] = s;
}</syntaxhighlight>
<syntaxhighlight lang="zkl">primes:=Utils.Generator(postponed_sieve);
primes.walk(20).println(); // first 20 primes
Line 6,416 ⟶ 7,232:
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes), this is a direct drop in for the above:
{{libheader|GMP}}
<syntaxhighlight lang="zkl">var [const] BN=Import.lib("zklBigNum"); // libGMP
bigPrimes:=Walker(fcn(p){ p.nextPrime().copy(); }.fp(BN(1)));</syntaxhighlight>
For example:
<syntaxhighlight lang="zkl">bigPrimes.walk(20).println(); // first 20 primes
bigPrimes.pump(Void,'wrap(p){ bigPrimes.n<=0d10_000 and p or Void.Stop }).println();</syntaxhighlight>
{{out}}
| |||