fork download
copy 
  1. program prim(output);
  2. const
  3.   PrimeLimit = 1000*1000*1000;//1;
  4. type
  5.   tLimit = 1..PrimeLimit;
  6. var
  7.   primes: array [tLimit] of boolean;
  8.  
  9. function BuildWheel: longInt;
  10. var
  11.   wheelprimes :array[0..13] of byte;
  12.   wheelSize,wpno,
  13.   pr,pw,i, k: LongWord;
  14. begin
  15.   pr := 1;
  16.   primes[1]:= true;
  17.   WheelSize := 1;
  18.  
  19.   wpno := 0;
  20.   repeat
  21.     inc(pr);
  22.     pw := pr;
  23.     if pw > wheelsize then
  24.       dec(pw,wheelsize);
  25.     If Primes[pw] then
  26.     begin
  27.       k := WheelSize+1;
  28.       for i := 1 to pr-1 do
  29.       begin
  30.         inc(k,WheelSize);
  31.         if k<primeLimit then
  32.           move(primes[1],primes[k-WheelSize],WheelSize)
  33.         else
  34.         begin
  35.           move(primes[1],primes[k-WheelSize],PrimeLimit-WheelSize*i);
  36.           break;
  37.         end;
  38.       end;
  39.       dec(k);
  40.       IF k > primeLimit then
  41.         k := primeLimit;
  42.       wheelPrimes[wpno] := pr;
  43.       primes[pr] := false;
  44.  
  45.       inc(wpno);
  46.       WheelSize := k;
  47.  
  48.       i:= pr;
  49.       i := i*i;
  50.       while i <= k do
  51.       begin
  52.         primes[i] := false;
  53.         inc(i,pr);
  54.       end;
  55.     end;
  56.   until WheelSize >= PrimeLimit;
  57.  
  58.  
  59.   while wpno > 0 do
  60.   begin
  61.     dec(wpno);
  62.     primes[wheelPrimes[wpno]] := true;
  63.   end;
  64.   BuildWheel  := pr+1;
  65. end;
  66.  
  67. procedure Sieve;
  68. var
  69.   sieveprime,
  70.   fakt : LongWord;
  71. begin
  72.   sieveprime := BuildWheel;
  73.   repeat
  74.     if primes[sieveprime] then
  75.     begin
  76.       fakt := PrimeLimit DIV sieveprime;
  77.       IF fakt < sieveprime then
  78.         BREAK;
  79.       repeat
  80.         primes[sieveprime*fakt] := false;
  81.         //Search next smaller possible prime
  82.         repeat
  83.           dec(fakt);
  84.         until primes[fakt];
  85.       until fakt < sieveprime;
  86.     end;
  87.     inc(sieveprime);
  88.   until false;
  89.   primes[1] := false;
  90. end;
  91.  
  92. var
  93.   prCnt,
  94.   i : LongWord;
  95. Begin
  96.   Sieve;
  97.   {count the primes }
  98.   prCnt := 0;
  99.   for i:= 1 to PrimeLimit do
  100.     inc(prCnt,Ord(primes[i]));
  101.   writeln(prCnt,' primes up to ',PrimeLimit);
  102. end.
Success #stdin #stdout 3.97s 978432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
50847534 primes up to 1000000000
https://ideone.com/WKv9qW
language:
Pascal (gpc 20070904)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!