Extensible prime generator: Difference between revisions
m
→{{header|Pascal}}: corrected. COllect primes for sieving was wrong implemented ( only first primes to 131071 were right )
(→OCaml: add) |
m (→{{header|Pascal}}: corrected. COllect primes for sieving was wrong implemented ( only first primes to 131071 were right )) |
||
Line 3,501:
=={{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,525 ⟶ 3,512:
<syntaxhighlight lang="pascal">
unit primsieve;
{$IFDEF FPC}
{$MODE objFPC}{$Optimization ON,ALL}
{$IFEND}
{segmented sieve of Erathostenes using only odd numbers}
Line 3,538 ⟶ 3,523:
function SieveSize :LongInt;
function Nextprime: Uint64;
function StartCount :Uint64;
function TotalCount :Uint64;
function PosOfPrime: Uint64;
Line 3,565 ⟶ 3,551:
{$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,611 ⟶ 3,597:
function InsertSievePrimes(PrimPos:NativeInt):NativeInt;
var
i,pr,loLmt : NativeUInt;
begin
i := 0;
Line 3,619 ⟶ 3,605:
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,634 ⟶ 3,622:
Begin
pr := FoundPrimes[i]*2+1;
svdeltaPrime := (pr-
end;
inc(PrimPos);
end;
LastInsertedSievePrime :=
result := PrimPos;
end;
Line 3,690 ⟶ 3,678:
SieveNum :=0;
CopyPreSieveInSieve;
//normal sieving of first block sieve
i := 1; // start with 3
repeat
Line 3,708 ⟶ 3,696:
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,812 ⟶ 3,799:
procedure CollectPrimes;
//extract primes to FoundPrimes
var
pSieve : pbyte;
Line 3,818 ⟶ 3,805:
i,idx : NativeUint;
Begin
FoundPrimesOffset := SieveNum*(2*cSieveSize);
FoundPrimesIdx := 0;
pFound :=@FoundPrimes[0];
Line 3,845 ⟶ 3,832:
end;
procedure SieveOneBlock;inline;
begin
CopyPreSieveInSieve;
Line 3,853 ⟶ 3,840:
end;
procedure NextSieve;inline;
Begin
SieveOneBlock;
Line 3,868 ⟶ 3,855:
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,899 ⟶ 3,891:
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>
| |||