1:
2:
3:
4:
5:
6:
7:
8:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:

C:\TEST>D:\DMX\M1864\DCC64 -b FastprimeQuadrupel.dpr
Embarcadero Delphi for Win64 compiler version 25.0
Copyright (c) 1983,2013 Embarcadero Technologies, Inc.
std.inc(632)
std.inc(632)
btypes.pas(200)
std.inc(632)
mp_conf.inc(175)
mp_types.pas(739)
mp_conf.inc(175)
std.inc(632)
mp_conf.inc(175)
std.inc(632)
isaac.pas(424)
mp_isaac.inc(101)
mp_prng.pas(198)
mp_bas64.inc(180)
mp_base.pas(11195)
std.inc(632)
mp_conf.inc(175)
std.inc(632)
mp_conf.inc(175)
mp_modul.pas(1761)
std.inc(632)
mp_conf.inc(175)
mp_prm16.inc(411)
mp_pbits.inc(262)
mp_prime.pas(2218)
mp_numth.pas(7667)
Uquadrupel.pas(70) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(71) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(72) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(73) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(80) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(84) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(86) Error: E2107 Operand size mismatch
Uquadrupel.pas(87) Error: E2107 Operand size mismatch
Uquadrupel.pas(99) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(100) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(101) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(102) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(132) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(147) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(151) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(152) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(157) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(185) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(238) Error: E2116 Invalid combination of opcode and operands
Uquadrupel.pas(276) Warning: W1058 Implicit string cast with potential data loss from 'TCaption' to 'AnsiString'
Uquadrupel.pas(285) Warning: W1057 Implicit string cast from 'AnsiString' to 'string'
Uquadrupel.pas(342) Warning: W1057 Implicit string cast from 'AnsiString' to 'string'
Uquadrupel.pas(342) Warning: W1057 Implicit string cast from 'AnsiString' to 'string'
Uquadrupel.pas(406)
FastprimeQuadrupel.dpr(5) Fatal: F2063 Could not compile used unit 'Uquadrupel.pas'                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110 + 20000000
Kandidaten = 4512
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111110 + 20000000
Kandidaten = 4657
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111151111110 + 20000000
Kandidaten = 4605
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 20,98 s 
----------                    

1:
2:

procedure s_mp_nextprime_sieve(safe: boolean; var n: mp_int);
  {-Compute the next prime >= n using a segmented sieve, safe prime if safe=true}                    

1:
2:
3:
4:

uses
  Winapi.Windows, winapi.Messages, system.SysUtils, system.Variants,   system.Classes, vcl.Graphics, vcl.Controls,
  vcl.Forms, vcl.Dialogs, vcl.StdCtrls, mp_base, mp_numth, mp_prng, mp_prime, mp_types, vcl.Buttons,
  Vcl.Samples.Spin;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:

Primzahlen bis .. 200560490130 ( 2*3*5*7*11*13*17*19*23*29*31 )
Prime numbers:      8028643010
Twin primes:         425177757
Prime triplets:       73990934
Prime quadruplets:     2166281
Prime quintuplets:      427251
Prime sextuplets:        14804

Elapsed time:  34.55 sec                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

program t_tt5;

{$i STD.INC}
{$i mp_conf.inc}

{$ifdef APPCONS}
  {$apptype console}
{$endif}

uses
  hrtimer,
  mp_prime, mp_base,
  mp_types;

var
  p: longint;
  HR: THRTimer;
  sieve: TSieve;
const
  PMAX = 8000000;
begin
  StartTimer(HR);
  prime_sieve_init(sieve, 2);
  repeat
    p := prime_sieve_next(sieve);
  until p>PMAX;
  writeln('Time [s]: ',ReadSeconds(HR):1:6);
  prime_sieve_clear(sieve);
end.

D:\Work\MPArith>t_tt5.exe
Time [s]: 0.048456                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

var
  p,cnt: longint;
  HR: THRTimer;
  sieve: TSieve;
  myprimes: array[1..63951] of longint; { primepi(800000) = 63951}
begin
  StartTimer(HR);
  prime_sieve_init(sieve, 2);
  cnt := 0;
  repeat
    p := prime_sieve_next(sieve);
    inc(cnt);
    myprimes[cnt] := p;
  until cnt=63951;
  writeln(p);
  writeln('Time [s]: ',ReadSeconds(HR):1:6);
  prime_sieve_clear(sieve);
end.

D:\Work\MPArith>t_tt5.exe
799999
Time [s]: 0.009524                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Primzahlberechnung: 0,2378 s 
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110 + 20000000
Kandidaten = 4385
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111110 + 20000000
Kandidaten = 4535
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111151111110 + 20000000
Kandidaten = 4490
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 8,719 s 
----------                    

1:
2:
3:

 
//ergeb:=mp_is_pprime(m3);
ergeb :=  mp_is_spsp_d(m3,2) and mp_is_slpsp(m3);                    

1:
2:
3:
4:
5:

  with primzahlen[1] do
  Begin
    prPrimZ :=3;
    prUebertrag := 3-rest;
  end;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 13,7 s                    

1:
2:
3:
4:
5:
6:
7:
8:
9:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982611
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730179140373
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982613
  = 13 · 85470085470085470085470085470085470085470085470085470085470085470085470085470085470085470096460201
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982617
  = 23 · 48309178743961352657004830917874396135265700483091787439613526570048309178743961352657004837129679
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982619
  = 673 · 1650982334489020967475648010566286940729734191844147267624236420670298827802542512795113092502203
Zeit: 30,2 s                    

1:

 mp_small_factor(m1,minteiler,maxteiler,teilerx);                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

const
    MAXTM3 = 512;       {maximaler kleiner Teiler für m3}
var
    tb: mp_digit;
...
            mp_div(m1,m2,m3);
            //Primzahltest des grossen Faktors  ergeb ist true, wenn Primzahl
            if teilerx <= MAXTM3 then begin
              mp_small_factor(m3,teilerx,MAXTM3,tb);
            end
            else tb := 0;
            ergeb:= (tb=0) and s_mp_is_psp2(m3);       //Fermattest                    

1:
2:
3:
4:
5:
6:
7:
8:
9:

const
{$IFDEF CPU64}
  groesse = 1000 * 1000;
  anzahl_primzahlen = 750 * 1000;
{$ELSE}
  groesse = 1000 * 1000;
  anzahl_primzahlen = 1800 * 1000;
{$ENDIF}
  MAXTM3 = 512;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

  prime_sieve_init(sieve, 7);
  i := 2;
  repeat
    p := prime_sieve_next(sieve);
    mp_mod_int(m4, p, rest);
    mp_mod_int(m4, 2 * p, rest2);
    with primzahlen[i] do
    begin
      prPrimZ := p;
      if (rest <> rest2) then
        prUebertrag := 2 * prPrimZ - rest
      else
        prUebertrag := prPrimZ - rest;
    end;
    Inc(i);
  until i > anzahl_primzahlen;// war vorher = -> die letzte primzahlen war 0 , nicht nett ;-)
  prime_sieve_clear(sieve);                    

1:
2:
3:
4:
5:
6:
7:
8:

//i ist der Index in die Primzahlen shl 8 aka *256 
    while (isieb <= groesse) do
    begin
      zahl[isieb] := ((zahl[isieb] + 1) and $000000FF) + i;
      Inc(isieb, p);
    end;
    inc(pPrim);
    inc(i,256);                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

const
  deltaP: array[1..4] of integer = (0, 2, 6, 8 );
...
if ((zahl[j] and $FF) = 1) and ((zahl[j + 2] and $FF) = 1) and
        ((zahl[j + 6] and $FF) = 1) and ((zahl[j + 8] and $FF) = 1) then
      begin
        Inc(testzahl);
        p := 1;
        repeat
          ergeb := False;
          //kleinen Faktor hervorkramen
          teilerx := primzahlen[Zahl[j + deltaP[p]] shr 8].prPrimZ;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 * 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 * 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 * 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:02.269
----------                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

Linux 64 fpc 3.1.1  ( experimentell )
...  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:02.407
----------
Win64 und wine 2 fpc 3.1.1
...   = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 3.308 s 
----------
Linux32 fpc 3.1.1
...   = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:04.273
----------
Win32 und wine 2 fpc 3.1.1
...   = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 4.809 s 
----------                    

1:
2:
3:

  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Anzahl Siebungen 105
Zeit: 00:00:02.314                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 * 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 * 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 * 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:07.963
Anzahl Siebungen   6
Anzahl Langtests   6094
TestBereich 58198140
----------
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127981
  = 113 * 9832841691248770894788593903638151425762045231071779744346116027531956735496558505408062930186823992133726647000983284169124877089478859390363815142576204523107177974434611602753195673549686912637
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127983
  = 11 * 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101329193453
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127987
  = 37 * 30030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030124895351
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127989
  = 193 * 5757052389176741508347725964306275187104202648244099021301093839953943580886586067933218192285549798503166378814047207829591249280368451352907311456534254461715601611974668969487622337363288192373
Zeit: 00:06:41.681
Anzahl Siebungen   362
Anzahl Langtests   377211
TestBereich 3511287780
----------                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:

Groesse Sieb = 2*3*5*7*....*17*19 = 9.699.690 ~40 Mb
Testzahl  '1' gefolgt von 149x'0'
----------
1.....01824150031  =   71 * 140845....39776761
1.....01824150033  =   61 * 163934....43018853
1.....01824150037   = 2767 *   3614....26318811
1.....01824150039   =   23 * 434782....66267393
Zeit: 00:02:40.802
Anzahl Siebungen   200
Anzahl Langtests   364418
Anzahl TestBereich 1833241410 // 500.000 Primzahlen
----------
 
 Zeit zum vorsieben  00:00:00.082
 Zeit zum 10x Sieben  00:00:00.811
  = 71 * 1408..  = 61 * 1639..  = 2767 * 36..  = 23 * 4347..
Zeit: 00:02:15.972 -> 135,972 - 16,22 => 119,752 / 297804 == 402 µs / Langtest
Anzahl Siebungen   200 -> 16,22 s
Anzahl Langtests   297804
Anzahl TestBereich 1833241410  //1.500.000 Primzahlen

 Zeit zum vorsieben  00:00:00.124
 Zeit zum 10x Sieben  00:00:00.843
  = 71 * 1408..  = 61 * 1639..  = 2767 * 36..  = 23 * 4347..
Zeit: 00:02:07.192 -> 127,192-16,86 s =110,332 -> 405 µs /Langtest
Anzahl Siebungen   200 -> 16,86s
Anzahl Langtests   272081
Anzahl TestBereich 1833241410  //2.500.000 Primzahlen

 Zeit zum vorsieben  00:00:00.230  // Primzahlen Suche langsam
 Zeit zum 10x Sieben  00:00:00.887
  = 71 * 1408..  = 61 * 1639..  = 2767 * 36..  = 23 * 4347..
Zeit: 00:01:59.447 = 119,447-17,74-0.230 = 101,477s/ 242129 = 419 µs
Anzahl Siebungen   200 -> 17,74
Anzahl Langtests   242129
Anzahl TestBereich 1833241410  //5.000.000 Primzahlen

 Zeit zum vorsieben  00:00:00.737  // Primzahlensuche langsam
 Zeit zum 10x Sieben  00:00:01.049
  = 71 * 1408..  = 61 * 1639..  = 2767 * 36..  = 23 * 4347..
 Zeit: 00:01:55.149 = 115,149-20,98-0,737  = 93,432s/ 199546 = 468 µs /Langzahltest
Anzahl Siebungen   200 -> 20,98s
Anzahl Langtests   199546
Anzahl TestBereich 1833241410 //16.777.215 Primzahlen ( 1 shl 24 -1) 
----------
Jetzt Sieb 10x
----------
10x Sieb - >10* 2*3*5...*17*19 =  96.996.900 x4Byte ~ 400 Mb
 Zeit zum vorsieben  00:00:00.966 // Vorsieb ist auch 400 Mb
 Zeit zum 10x Sieben  00:00:09.520
  = 71 * 1408..  = 61 * 1639..  = 2767 * 36..  = 23 * 4347..
 Zeit: 00:01:48.360 0 108,36s- 19,046-0,966 = 88,348s => 443 µs
Anzahl Siebungen   20 sein -> 19,046s
Anzahl Langtests   199546
Anzahl TestBereich 1842941100  //16.777.215 Primzahlen ( 1 shl 24 -1)

Bei 200 Stellen dauert ein Lanzahltest etwa  920 µs 
Bei 250 Stellen dauert ein Lanzahltest etwa 1650 µs, die habe ich nur einmal gemessen ;-)                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

Stellenzahl         50
Zeit: Vorsieben    00:00:03.586 // für 1 shl 24 -1 Primzahlen und Bestimmung der Überträge
Zeit: Sieben       00:00:02.001 // Zeit für sieben und finden(zählen)
Anzahl Siebungen   15
Anzahl Testquadr   20358
Anzahl Langtests   0
       TestBereich 145495350
----------
Stellenzahl         150
Zeit: Vorsieben    00:00:08.611
Zeit: Sieben       00:00:01.988
Anzahl Siebungen   15
Anzahl Testquadr   20561
Anzahl Langtests   0
       TestBereich 145495350
----------
Stellenzahl         450
Zeit: Vorsieben    00:00:24.994
Zeit: Sieben       00:00:01.988
Anzahl Siebungen   15
Anzahl Testquadr   20352
Anzahl Langtests   0
       TestBereich 145495350                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

const
   quadratzahl = 13;
   quadrate : array[1..13] of integer = (9,27,81,3*3*3*3,49,7*7*7,121,169,289,361,23*23,29*29,31*31);
begin
  ...
  for i:=1 to quadratzahl do begin
  mp_mod_int(m4, quadrate[i], rest);
  mp_mod_int(m4, 2 * quadrate[i], rest2);
  with primzahlen[i+1] do
  begin
    prPrimZ := quadrate[i];
    if (rest <> rest2) then
      prUebertrag := 2 * prPrimZ - rest
    else
      prUebertrag := prPrimZ - rest;
  end;
  end;
  ...
end;                    

1:
2:
3:
4:
5:
6:
7:

const
   quadratzahl = 15;
   quadrate : array[1..quadratzahl] of integer = (2*3,  3*7,  3*11,  3*13,  3*17,
                                                        7*7,  7*11,  7*13,  7*17,
                                                             11*11, 11*13, 11*17,
                                                                    13*13, 13*17,
                                                                           17*17);                    

1:
2:

                  GP/PARI CALCULATOR Version 2.9.3 (released)
          amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version                    

1:
2:
3:

_TEST:  begin
          mp_set(r,ord(s_mp_is_psp2(v1)) and 1);
        end;                    

1:
2:

    mp_inc(m1);
    mp_inc(m4);                    

1:
2:
3:
4:
5:

//nachfolgende Quadrupelzahl
              mp_add_d(m1, 2, m1);
              mp_mod_int(m1, 5, rest);
              if rest = 0 then
                mp_add_d(m1, 2, m1);                    

1:

Zeit: 00:00:04.395                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

  100    53397971      43,   1291,      7,    463     00:00:03.398
  101    77526031       7,      3,   3769,      3     00:00:04.662
  102   358907441    1481,      7,    359,   1699     00:00:20.449
  103   118981061    9421,   7109,   6947,      7     00:00:07.031
  104    99900031      19,      3,     37,      3     00:00:06.102
  105    61471311       3,      7,      3,     37     00:00:04.189
  106    22944281       7,     19,     47,    127     00:00:01.915
  107     4261061      31,      7,   1031,     11     00:00:00.761
  108   313530491      31,     11,     13,     19     00:00:21.028
Zeit: 01:09.975                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

  100    53397971      43,   1291,      7,    463     00:00:01.685
  101    77526031       7,      3,   3769,      3     00:00:02.364
  102   358907441    1481,      7,    359,   1699     00:00:10.356
  103   118981061    9421,   7109,   6947,      7     00:00:03.539
  104    99900031      19,      3,     37,      3     00:00:03.093
  105    61471311       3,      7,      3,     37     00:00:02.075
  106    22944281       7,     19,     47,    127     00:00:00.925
  107     4261061      31,      7,   1031,     11     00:00:00.324
  108   313530491      31,     11,     13,     19     00:00:10.424
  109    18090611     109,   9463,     17,    563     00:00:00.796
  110    20713731       3,      7,      3,     29     00:00:00.869
  111    46265411      59,    809,     17,   1163     00:00:01.725
  112   140371061     787,   2459,     11,    887     00:00:04.801
  113    76378171       7,      3,     31,      3     00:00:02.756
  114   137102771      19,   4129,   3739,    521     00:00:05.150
  115   181983221     857,     17,    151,     11     00:00:06.984
  116   624238811      43,    179,     19,   2789     00:00:23.886
Zeit: 01:21.959                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Zuvor:
  301  1557971731    4349,     11,   3847,     13     00:09:36.374
jetzt:
  301  1557971731    4349,     11,   3847,     13     00:08:22.480
  302   250233211       7,     97,     19, 152419     00:01:36.130
  303  1800073801  303917,     79,     17,     43     00:09:55.318
  304  4587564621    3923,      3,    269,      3     00:24:58.628
  305  2078310421      47,     53,   5591,  13721     00:11:28.176
  306  1530771211      79,  26029,   1423,   1381     00:08:38.098
  307  1386249451       7, 849221,     11,     43     00:07:49.874
  308   407647731     661,      3,     13,      3     00:02:31.984
  309  4995074881      13,     43,      7,   1039     00:27:41.190                    

1:
2:
3:

  {$ifdef FPC}
     cmem,
  {$endif}                    

1:
2:
3:
4:
5:

  300   492302551   13873, 694747,    827,     11     00:01:03.527
  301  1557971731    4349,     11,   3847,     13     00:03:04.191
  302   250233211       7,     97,     19, 152419     00:00:38.153
  303  1800073801  303917,     79,     17,     43     00:03:36.680
  304  4587564621    3923,      3,    269,      3     00:09:04.113// vorher 27 min                    

1:
2:
3:

  379   30999026611   77317,  23011,      7, 325153  01:36:46.778
..oder mal schnell..
  383     744300811    7129,     23, 372803,      7  00:02:42.611                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:

  310    6829816651      17      19      13       7     00:13:47.536
  311    8672563641   32771       3      23       3     00:17:28.398
  312    1196632831       7     173      41  297397     00:02:37.840
  313    3577075021    1487      31      17    1657     00:07:23.219
  314    1552863351       7       3      11       3     00:03:20.270
  315    1731173191      53      43       7  456451     00:03:39.699
  316    7789036631       3      13       3      17     00:16:04.655
  317    1293664111    4229  118043      17   32009     00:02:49.689
  318    4421143201      83      13  306167   70823     00:09:16.782
  319     379099141     163    1361      31     293     00:00:58.497
  320    1077897001   84307      97      17     503     00:02:26.936
  321     266732401       7   14411      31  303529     00:00:43.551
  322    3579133291      17       7  117503      13     00:07:53.516
  323     406839271     173    6607     433     877     00:01:04.490
  324    2470682971      47    4409      13       7     00:05:33.624
  325    1360504141     257    1723   31247     223     00:03:08.113
  326     753438931    6473   11923      31      47     00:01:49.741
  327    2522373301    7129      11  337081     277     00:05:41.711
  328   12710554381      19     101    7537       7     00:28:18.686
  329    3377692841       3     223       3   41243     00:07:48.519
  330   11671406551      37       7   14851    1741     00:26:43.830
  331    2019134001   11287       3   65519       3     00:04:46.657
  332    3411859471  533543      19    1913      43     00:08:02.532
  333    1716096331       7      71      11    4243     00:04:10.306
  334    3671628061     811      17   10987    2017     00:08:40.648
  335    2960662591      59   20903      29      53     00:07:04.541
  336    1712327341  410899      11     397      23     00:04:09.730
  337    1930221001      53      17     103     173     00:04:44.619
  338    3523723741     271      11     167      23     00:08:37.569
  339    9699771181      31     109     157      13     00:23:36.797
  340    4213608211       7      11      79    1031     00:10:28.885
  341    8429248501  770239     197   13523       7     00:20:50.745
  342    5968548751      13      19  517289   11131     00:14:56.310
  343    6663542761     229      61     751     941     00:16:42.335
  344    2161616371    1151  148549       7     239     00:05:34.687
  345     348959941    1607     227      43    2909     00:01:05.127
  346    5845745911    2963      23  136573  687061     00:14:53.270
  347    1068546631    5653      37      19   84559     00:02:53.898
  348     802685791     277      47      11    1499     00:02:14.465
  349   10806706711      19      23      41     541     00:28:08.244
  350    5050331641     967    3347       7     283     00:13:20.822
  351    2129154751      89       7   78487      13     00:05:44.928
  352   10671258691  198859   16139       7  244129     00:28:12.834
  353   11928307951      11    6151      17     109     00:31:32.000
  354    2150049641       3      17       3  264529     00:05:51.343
  355    4309780261     827   13331  307823     263     00:11:33.736
  356    2815760071      71     929       7  130477     00:07:41.966
  357    2389735951     101      41      37     487     00:06:41.236
  358    9837132721     599      37     127      41     00:27:07.692
  359    8908659941       3     569       3   20029     00:24:44.814
  360    4354219861  986351  713311    2377      59     00:12:14.941
  361    9401736631     199    1951       7    6397     00:26:29.980
  362    6564346381  752651      11       7      13     00:18:45.009
  363    4635585421       7      23      31    2381     00:13:35.053
  364      56972091       7       3      17       3     00:00:22.629
  365   13842035011      31     853      23      11     00:39:29.264
  366     895914631   21613   13249       7      13     00:02:46.324
  367     142525501       7      11   26177   11681     00:00:36.584
  368    1492888441   10883       7    1327      73     00:04:35.252
  369    5441746261   60859      41     127  580303     00:16:06.237
  370    4014172831  349963     229    2011      13     00:11:59.377
  371     369923161      13    4483     919   21347     00:01:18.277
  372    1624753561     733  185021      31   88681     00:04:59.141
  373     154327561  948971      61   11777      19     00:00:39.456
  374    5790998111       3      67       3       7     00:17:22.117
  375   13956960661     199     179     991      61     00:42:18.048
  376    2190540811     211    2111    6199   11059     00:07:00.570
  377    9670222751       3    7507       3      11     00:29:37.381
  378    1706225941  309403       7     331   42569     00:05:22.341
  379   30999026611   77317   23011       7  325153     01:36:46.778
  380   10343087851      43  268573       7      53     00:32:23.573
  381    1288532611      43      13      71     593     00:04:11.303
  382    8160019131      17       3     179       3     00:25:44.084
  383     744300811    7129      23  372803       7     00:02:42.611
  384   50640221281      11    5087      17    6389     03:04:11.541
  385    9435147871      59     389      13     127     00:32:35.248
  386   22052425381     251     139   60383      67     01:14:12.670
  387    1122696751     109    5783      73      19     00:03:48.219
  388    7966788431       3      59       3       7     00:27:02.082
  389   12164917141     241     563     199     379     00:41:06.283
  390    3867874651  804031      31      17    2053     00:12:52.925
  391     696184471     157   12163      11      67     00:02:28.904
  392    9211348231      59      17    4493      29     00:30:22.536
  393     587329801    2267     103      29   18947     00:02:10.300
  394   11544611671      19      11      13      41     00:38:49.645
  395    5120524981      19    4643    4663      59     00:17:31.159
  396    3046926091   39703    9887      23      13     00:10:34.664
  397    7470846631  425233     241      37  690119     00:25:48.414
  398    7373872681  182101      11      19   57397     00:25:41.418
  399    3356559061     233    2521      13     113     00:11:51.837
  400     609453511   28349   13781       7     367     00:02:22.690
  401    2401690261     487      19      71   16561     00:08:34.277
  402     221472831     911       3      29       3     00:00:59.231
  403   13388267161      17     149    1061     131     00:47:12.809                    

1:
2:
3:
4:
5:

 tChkListItem = record
    clSiebNr,     // Anzahl die Siebe seit Startzahl // also ist wahre Zahl Startzahl +clSiebNr*2*groesse
    clOffset  : LongWord; // ins aktuelle Sieb
    clquadTeil:tquadTeiler; // die 4 kleinen Teiler
  end;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

  200     292710691     509,     31,   3313, 159671  00:00:35.467
  201      35078311      17,  57493,     11,    419  00:00:11.095
  202      12830011   17183,     13,   2087, 423127  00:00:09.238
  203      37811851    2081,  36563,     17,   4679  00:00:11.333
  204     173238931     367,  56737,   2647,     17  00:00:23.733
  205     181105241       3, 851231,      3,   2917  00:00:24.355
  206      69468391      31,     19,  75931,    571  00:00:13.742
  207     517728691  842077,   9137,    349,      7  00:00:55.993
  208     899820511      17,   3037,      7,    887  00:01:41.153
  209     105308761      37,     11,   3079,   5323  00:00:21.507
Zeit: 00:05:51.675                    

1:
2:
3:
4:
5:
6:
7:

  200     292710691     509,     31,   3313, 159671  00:00:46.523
  201      35078311      17,  57493,     11,    419  00:00:13.016
  202      12830011   17183,     13,   2087, 423127  00:00:10.669
  203      37811851    2081,  36563,     17,   4679  00:00:13.455
  204     173238931     367,  56737,   2647,     17  00:00:29.778
  205     181105241       3, 851231,      3,   2917  00:00:30.880
  206      69468391      31,     19,  75931,    571  00:00:17.055                    

1:
2:
3:

n=100   k =     2'811'012'357
n=200   k =    44'976'197'718
n=500   k = 1'756'882'723'368                    

1:
2:
3:
4:

100  816926830
200  805201750
400  832790860 < wundersam wenige 
800  798116980                    

1:

403   13388267161      17     149    1061     131     00:47:12.809                    

1:

  400  34993836001       0,      0,      0,      0     00:13:21.804                    

1:

  400  34993836001       0,      0,      0,      0     00:12:30.458                    

1:

  553  1447073137021     11:53:33.600                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:

program GMP_Test;
//testet die Laufzeit von mpz_probab_prime_p bei
//verschiedenen Stellenzahlen
{$IFNDEF FPC}
  {$Apptype CONSOLE}
{$ELSE}
  {$MODE DELPHI}
{$ENDIF}

uses
  sysutils,gmp,mp_base, mp_numth, mp_prng, mp_prime, mp_types;
type
  tTestWerte = record
                 twSZ,              //Stellenzahl
                 twVs : NativeUint; //Verschiebung aka Offset
               end;
const
 {cTestwerte : array[1..10] of tTestWerte =
              ((twSz: 100;twVs:349781731),
               (twSz: 200;twVs:21156403891),
               (twSz: 300;twVs:140159459341),
               (twSz: 400;twVs:34993836001),
               (twSz: 500;twVs:883750143961),
               (twSz: 600;twVs:1394283756151),
               (twSz: 700;twVs:547634621251),
               (twSz: 800;twVs:3125423484751),
               (twSz: 900;twVs:430772369311),
               (twSz:1000;twVs:1657378832463));
}
cTestwerte : array[1..10] of tTestWerte =
              ((twSz: 100;twVs:2191),
               (twSz: 200;twVs:5491),
               (twSz: 300;twVs:4681),
               (twSz: 400;twVs:7081),
               (twSz: 500;twVs:15721),
               (twSz: 600;twVs:2161),
               (twSz: 700;twVs:20251),
               (twSz: 800;twVs:9511),
               (twSz: 900;twVs:6991),
               (twSz:1000;twVs:19411));
{$IFDEF CPU32}
  runden = 25;
{$ENDIF}
{$IFDEF CPU64}
  runden = 100;
{$ENDIF}
var
   x :mpz_t;
   y: mp_int;

procedure TestlaufMpArith(var TestZahl:mp_int);
var
   T1,T0: TDateTime;
   i: integer;
Begin
 t0:= time;
 For i := 1 to runden do
   s_mp_is_psp2(TestZahl);
 t1:= time;
 Writeln(86400*1000*(T1-T0)/runden:8:6,' ms');
end;

procedure TestlaufGMP(var TestZahl:mpz_t);
var
   T1,T0: TDateTime;
   i: integer;
Begin
 t0:= time;
 i := 1;
 For i := 1 to runden do
   mpz_probab_prime_p(TestZahl, 0);
 t1:= time;
 Writeln(86400*1000*(T1-T0)/runden:8:6,' ms');
end;

var
  i : integer;
begin

 mpz_init(x);
 writeln('GMP');
 For i := low(cTestwerte) to High(cTestwerte) do
 Begin
   mpz_set_ui(x,10);
   with cTestwerte[i] do
   Begin
     mpz_pow_ui(x,x,twSz-1);
     mpz_add_ui(x,x,twVs);
     write(twSz:5,'  ');
   end;
   TestlaufGMP(x);
 end;
 mpz_clear(x);

 writeln;
 writeln('MpArith');
 mp_init(y);
 For i := low(cTestwerte) to High(cTestwerte) do
 Begin
   mp_set(y, 10);
   with cTestwerte[i] do
   Begin
     mp_expt_int(y,twSz-1,y);
     mp_add_d(y,twVs,y);
     write(twSz:5,'  ');
   end;
   TestlaufMpArith(y);
 end;
 mp_clear(y);

end.                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:

CPU64
# ./GMP_Test
GMP
  100  0.030000 ms
  200  0.170000 ms
  300  0.500000 ms
  400  1.080000 ms
  500  2.050000 ms
  600  3.590000 ms
  700  5.340000 ms
  800  7.630000 ms
  900  10.660000 ms
 1000  14.320000 ms

MpArith
  100  0.150000 ms
  200  0.880000 ms
  300  3.400000 ms
  400  6.990000 ms
  500  12.950000 ms
  600  29.610000 ms
  700  39.780000 ms
  800  52.050000 ms
  900  77.090000 ms
 1000  104.640000 ms

CPU32
# ./GMP_Test
GMP
  100  0.120000 ms
  200  0.880000 ms
  300  2.760000 ms
  400  5.920000 ms
  500  10.720000 ms
  600  18.560000 ms
  700  28.560000 ms
  800  33.480000 ms
  900  50.280000 ms
 1000  82.480000 ms

MpArith
  100  0.440000 ms
  200  3.000000 ms
  300  10.720000 ms
  400  22.400000 ms
  500  40.600000 ms
  600  184.160000 ms
  700  215.800000 ms
  800  278.840000 ms
  900  554.600000 ms
 1000  674.480000 ms                    

1:
2:
3:

 10^500 = 1661 Bits =  53 mp_digits
 10^600 = 1994 Bits =  64 mp_digits;
10^1000 = 3322 Bits = 107 mp_digits                    

1:
2:

 mp_t3m_cutoff  := 2*mp_mul_cutoff;
 mp_t3s_cutoff  := 2*mp_sqr_cutoff;                    

1:
2:

 mp_t3m_cutoff  := 4*mp_mul_cutoff;
 mp_t3s_cutoff  := 4*mp_sqr_cutoff;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

         D3/16    FPC32   D18/32    FPC64    FPC32/T=4K
  100    1.342    1.938    2.459    1.093    1.950
  200    6.541    6.042    7.057    4.074    5.551
  300   17.410   14.102   20.856    7.424   14.079
  400   39.333   28.126   45.369   14.153   28.101
  500   77.455   52.632   86.937   24.796   52.558
  600  128.781   95.760  150.708   48.929   98.861
  700  199.945  142.172  227.475   69.307  147.441
  800  293.470  205.109  336.141   98.148  210.664
  900  424.481  327.736  476.608  170.889  287.117
 1000  568.588  456.911  642.765  207.466  385.704                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:

program FindeQuadrupel;
//Sieben nach Quadrupeln der Form 30*n+(11,13,17,19)
//also muss Mod30 aus Menge [11,13,17,19] sein
//die Faktoren bestimmen den Abstand zum nächsten Element aus der Menge
//Beispiel 1 -> 0R 1 hat bei *11, *13, *17, *19, einen Treffer,
//wieder bei *(30+11-19) = *22
//faktorenmässig Start bei +11,dann +2+4+2+22,+2+4+2+22 ....
//Also 4 Treffer bei einem Schritt von 30.
//ich bestimme die Faktoren einmal und dann wird nur noch addiert
//
//Vergleich mit https://oeis.org/A007530/b007530.txt

{$IFDEF FPC}
  {$MODE DELPHI}
  {$OPTIMIZATION ON,REGVAR,CSE,PEEPHOLE}
  //{$R+,I+,O+} //gibt kein mecker mehr...
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}
uses
  sysutils;
type
  tSieveElem = NativeUint;

  tDelta30 = array[0..3] of  NativeUint;
  tMulOfs = record
              moMul,moOfs: byte;
            end;
  tMulPosArr = array[0..3] of  tMulOfs;

  tPrimMod30   =packed record
//                 deltaP     : p[n-1]-p[n] (delta DIV30 + delta MOD30 )
                   pm30Offset   : LongWord;  //Uebertrag bis 22 * p DIV 30
                   pmNextSivbNr : word;
                   pm30AktIdx,
                   pm30Delta  : byte;//delta DIV30 shl 3 + delta MOD30Idx
                 end;
  tpPrimMod30 = ^tPrimMod30;

const
  cMulOfs : array [0..7]of tMulPosArr =
    (((moMul: 2;moOfs:0),(moMul: 4;moOfs: 0),(moMul: 2;moOfs:0),(moMul:22;moOfs: 1)), // 1
     ((moMul: 4;moOfs:1),(moMul: 8;moOfs: 2),(moMul: 4;moOfs:1),(moMul:14;moOfs: 3)), // 7
     ((moMul: 6;moOfs:2),(moMul:16;moOfs: 6),(moMul: 6;moOfs:2),(moMul: 2;moOfs: 1)), //11
     ((moMul:12;moOfs:5),(moMul: 4;moOfs: 2),(moMul:12;moOfs:5),(moMul: 2;moOfs: 1)), //13
     ((moMul:12;moOfs:7),(moMul: 4;moOfs: 2),(moMul:12;moOfs:7),(moMul: 2;moOfs: 1)), //17
     ((moMul: 6;moOfs:4),(moMul:16;moOfs:10),(moMul: 6;moOfs:4),(moMul: 2;moOfs: 1)), //19
     ((moMul: 4;moOfs:3),(moMul: 8;moOfs: 6),(moMul: 4;moOfs:3),(moMul:14;moOfs:11)), //23
     ((moMul: 2;moOfs:2),(moMul: 4;moOfs: 4),(moMul: 2;moOfs:2),(moMul:22;moOfs:21)));//29

  cMod30ToIdx : array[0..29] of byte =
                 (111,0,111,111,111,111,111,1,111,111,111,2,111,3,111,
                  111,111,4,111,5,111,111,111,6,111,111,111,111,111,7);

  cIdxToMod30 : array[0..7] of byte = (1,7,11,13,17,19,23,29);

//Anzahl der Bits eines Sieb-Elementes
  cBitSize = SizeOf(tSieveElem)*8;
  cAndMask = cBitSize-1;


//Abfolge der Streichpositionen
//Nextpos = k*p DIV 30
//idx = cMod30ToIdx[p MOD 30]
//i = 0;
//repeat
//  NextPos = Lastpos + (cStartOffset[idx][i] + (p DIV 30)*cFaktoren[idx][i]);
//  i = (i+1) AND 3;
//until JetztIstAberGut;

//1*151 == 5*30+1
//idx -> 0
//Ausnahme erster Wert dort NextPos = NextPos shr 1;
// 11*151 = 1661 = 55*30+11
// i:= 3;
//  NextPos = (1 + 5* 22) shr 1;//(1 +110) shr 1 -> 55
//  i = (i+1) AND 3 => 0
// 13*151 = 1963 = 65*30+13
//  NextPos = 55+(0 + 5* 2);//55+10 -> 65
//  i = (i+1) AND 3 => 1
// 17*151 = 1963 = 85*30+17
//  NextPos = 55+(0 + 10* 2);//65+20 -> 85
//  i = (i+1) AND 3 => 2
// 19*151 = 1963 = 65*30+19
//  NextPos = 85+(0 + 5* 2);//85+10 -> 95
//  i = (i+1) AND 3 => 3
// (30+11)*151 = 6191 = 206*30+11
//  NextPos = 95+(1 + 5* 22);//95+111 -> 206
//  i = (i+1) AND 3 => 0
// (30+13)*151 = 6493 = 216*30+13
//  NextPos = 206+(0 + 5* 2);//206+10 -> 216

//Ein Sieb x64-bit
//  cSiebGroesse = 500*1000*1000*1000;//->4671000 in 521s/57089 Primz

//mehrfach mit Übertrag gesiebt 2000*cSiebgroesse
//Anzahl Primzahlen 57089  Anzahl      : 4671012    210s

// etwa 1 MB
  cSiebGroesse  = 64*30*130208;//2.5e8-640

  cPrimeMax =63245;//trunc(sqrt(MaxZahl))+1;
var
  SiebMod30 : array[0..(cSiebGroesse-1) DIV 30 DIV cBitSize] of tSieveElem;
  Prim30List :array[0..11895200] of tPrimMod30;
  PrimSieb  : array of boolean;
  T0,T1: TDAteTime;
  gblP30,
  Prim30idx,
  LastPrime : longWord;

  tmpDelta30:tDelta30;

function Auszaehlen:Longint;
var
  i:NativeUInt;
  elem:tSieveElem;
begin
  result := 0;
  Begin
    For i := Low(SiebMod30) to High(SiebMod30)-1 do
    Begin
      //Bits umkehren
      elem := NOT SiebMod30[i];
      repeat
        inc(result,elem AND 1);
        elem := elem shr 1;
      until elem  = 0;
    end;
    // die letzten Bits zaehlen
    elem := NOT SiebMod30[High(SiebMod30)];
    i := High(SiebMod30)*30*cBitsize;
    while i < cSiebGroesse do
    Begin
      inc(result,elem AND 1);
      elem := elem shr 1;
      inc(i,30);
    end;
  end;
end;

procedure MulListErstellen(p30:LongWord);
var
  pMulPos : ^tMulOfs;
begin
  pMulPos := @cMulOfs[p30 AND 7][0];
  //p30 zu p DIV 30
  p30 := p30 shr 3;
  with pMulPos^ do
    tmpDelta30[0] := moOfs+p30*moMul;
  inc(pMulPos);
  with pMulPos^ do
    tmpDelta30[1] := moOfs+p30*moMul;
  inc(pMulPos);
  with pMulPos^ do
    tmpDelta30[2] := moOfs+p30*moMul;
  inc(pMulPos);
  with pMulPos^ do
    tmpDelta30[3] := moOfs+p30*moMul;
end;
procedure PrimSieben;
var
  i,p: NativeInt;
Begin
  p := 2;
  repeat
    i := p*p;
    while i <= cPrimeMax do
    Begin
      PrimSieb[i] := true;
      inc(i,p);
    end;
    repeat
      inc(p);
    until NOT PrimSieb[p]
  until (p*p) >cPrimeMax;
end;

procedure PrimListeErstellen;
var
  i: NativeInt;
  p30,p30Idx,DIV30,Aktidx,Last30Prime: NativeUInt;
Begin
  T0 := now;
  setlength(PrimSieb,cPrimeMax+1);
  PrimSieben;

  Prim30idx   := 0;
  LastPrime   := 1;
  Last30Prime := 0;//==  1;
  For i := 7 to cPrimeMax do
    IF Not PrimSieb[i] then
    Begin
      DIV30 := i DIV 30;
      p30Idx := cMod30ToIdx[i-30*DIV30];
      p30 := DIV30 shl 3+p30Idx;
      MulListErstellen(p30);
      //>>ersten Offset bestimmen
      IF cMulOfs[p30Idx][3].moMul = 2 then
      Begin
        inc(DIV30,tmpDelta30[0]);
        Aktidx:= 1
      end
      else
      Begin
        DIV30:= tmpDelta30[3] shr 1;
        Aktidx:= 0;
      end;
       //<<ersten Offset bestimmen

      with Prim30List[Prim30idx] do
      Begin
        pm30Offset:= Div30;
        pm30Delta := p30-Last30Prime;
        pm30AktIdx:= Aktidx;
      end;
      inc(Prim30idx);
      if Prim30idx>High(Prim30List) then
      Begin
        BREAK;
      end;
      Last30Prime:= p30;
      LastPrime := i;
    end;
  dec(Prim30idx);
  setlength(PrimSieb,0);
  T1 := now;
  writeln('Anzahl Primzahlen ',Prim30idx,' Letzte PrimZahl ', lastPrime);
  Writeln('Laufzeit sieben',FormatDateTime('S.ZZZ',T1-T0));
end;

procedure EinmalSieben(var Prim30:tPrimMod30);
var
  p30,mytmp,AktIdx: NativeUInt;
begin
   with Prim30 do
   Begin
     MulListErstellen(gblP30);
     p30 := pm30Offset;
     AktIdx := pm30AktIdx;
   end;
  //Jetzt einfaches markieren und addieren
  //number of the highest Bit (High(SiebMod30)+1)*cBitSize-1
  while p30 < cSiebGroesse DIV 30 do
  Begin
    mytmp := p30 DIV cBitSize;
    SiebMod30[mytmp]:= SiebMod30[mytmp] OR (tSieveElem(1) shl (p30 AND cAndMask));
    inc(p30,tmpDelta30[AktIdx]);
    AktIdx := (AktIdx + 1) AND 3;
  end;
  with Prim30 do
  Begin
     pm30Offset:= p30-cSiebGroesse DIV 30;
     pm30AktIdx := AktIdx;
   end;

end;

function AlleSieben:longint;
var
  pPL : tpPrimMod30;
  i,k,cnt : NativeInt;

begin
  k := 0;
  cnt := 0;
repeat
  fillchar(SiebMod30,SizeOf(SiebMod30),0);
  i := 0;
  pPL := @Prim30List[0];
  gblP30 := 0;// == 1
  repeat
      inc(gblP30,pPL^.pm30Delta);
      If pPL^.pm30Offset < cSiebGroesse DIV 30 then
        EinmalSieben(pPl^)
      else
        dec(pPl^.pm30Offset,cSiebGroesse DIV 30);
    inc(pPL);
    inc(i);
  until i > Prim30idx;
  inc(cnt,Auszaehlen);
  inc(k);
until k >=8;//2000;
  result := cnt;
end;

var
  cnt:NativeUInt;
BEGIN
  PrimListeErstellen;
  cnt := AlleSieben;

  writeln('Limit         : ',cSiebGroesse);
  writeln('Suchfeldlimit : ',(High(SiebMod30)+1)*30*cBitSize);
  writeln('Anzahl        : ',cnt);
end.
(*
//i386
Limit         :16*(250e6-640)
Suchfeldlimit : 4000000320
Anzahl        : 85911

real  0m1.451s


Anzahl Primzahlen 57089 Letzte PrimZahl 707197
Laufzeit sieben 0.004
499.99e9 fast 500e9
Anzahl        : 4670987
real  3m31.657s -> 212 Sekunden

*)                    

1:
2:
3:
4:
5:
6:
7:
8:

type
tPrimMod30   =packed record
//                 p30   = (p DIV 30 shl 3)+ cMod30ToIdx[p Mod 30]
                   pm30Offset   : LongWord;  //Uebertrag bis 22 * p DIV 30
                   pmNextSivbNr : word;      // Wenn siebnr erreicht dann erst damit sieben
                   pm30AktIdx,
                   pm30Delta  : byte;//delta DIV30 shl 3 + delta MOD30Idx (== p30[n]-p30[n-1] )
                 end;                    

1:
2:

while liste.count>50 do begin
end;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:

#INCLUDE "windows.bi"
#INCLUDE "vbcompat.bi" 
  

 DIM AS INTEGER i,j,C,COUNT,XX,TT,A,PP,QZ,U,RR ,CON , n ,maxP , STC
 DIM AS LONGINT Start,ST,STT
 DIM AS STRING FF,FF1,FF2,FF3
 DIM AS BYTE zaehler
 
 FF=CURDIR
 FF2=FF+"\primes.txt"
 FF3=FF+"\QuadR.txt" //Quelldatei der 4Tupel 101 bis 9699690 , welche ab 23 erst Teiler haben, sind 36855 Stück

 
 REDIM Q(36855) AS INTEGER
 REDIM QC(36855) AS INTEGER
 
 INPUT " - 10^n+.... - Exponent n";n
 INPUT "Start Milliarden";Start:Start=Start*1000000000
 INPUT "Stop  Milliarde ";ST:St=St*1000000000
 INPUT "Primzahlen ins Sieb ab 100000 bis 80 M";maxP
 maxP=INT (maxP/log(maxP)) // Abschätzung der Anzahl für maxP
 
 RR=1
 FOR J=1 TO n
 RR=(RR*10) MOD 96996900   // 10 ^ n MOD 96996900  = 10 Block a 9699690 wegen Rasterversatz 
 NEXT J
 
 Start= (Start \ 96996900) * 96996900 - RR <- siehe hier
 
 OPEN FF3 FOR INPUT AS #1  //einlesen der 4Tupel
 FOR C=1 TO 36855
 INPUT #1,A:Q(C)=A+8
 
 NEXT C
 CLOSE #1

 
 
 REDIM P(maxP) AS INTEGER   // einlesen der Primteiler bis maxP
 
 OPEN FF2 FOR INPUT AS #2
 FOR C=1 TO maxP
 INPUT #2,A
 P(C)=A
 NEXT C
 CLOSE #2
 REM Erstellung der RESTTABELLE
 
 REDIM R(maxP) AS INTEGER
 
 FOR I=1 TO maxP   // ermitteln der Resttabelle aller Primteiler für 10^n+Startwert, für Verschiebungsstart des Blockes nötig
 RR=1
 FOR J=1 TO n
 RR=(RR*10) MOD P(I)
 NEXT J
 R(i)=(RR+Start) MOD P(I)   // Der Restwert für 10^n+Start MOD Primteiler 
 NEXT I
  
 
 REDIM R2(maxP) AS INTEGER  // ersten 3000 Teiler Restwert für 96996900 Primteiler für die Unterblockverschiebung 9699690
 
 FOR I=1 TO 3000
 R2(I)=9699690 MOD P(I)
 NEXT I 
 
 FOR I=3001 TO maxP // ab 3001 Teiler Restwert für 96996900 Primteiler für die Unterblockverschiebung 96996900
 
 R2(I)=96996900 MOD P(I)
 NEXT I 
 
 REM ENDE
 
 REM Erstellung der RESTTABELLE 2  - 9699690 MOD P
 
 REM BEGIN SIEBEN
 CLS
 
 B0:
 STC=INT(Start/10^11) // Schnitt volle 100 Mrd Blöcke für paralelles PRPing mit PFGW.exe
 FF1=FF+"\"+STR(n)+"."+STR(STC)
 
 // Datei PFGW Style erstellung

 IF FILEEXISTS(FF1) THEN OPEN FF1 FOR APPEND AS #9 ELSE OPEN FF1 FOR OUTPUT AS #9
 
 PRINT #9,"ABC 10^";n;"+$a & 10^";n;"+$a+2 & 10^";n;"+$a+6 & 10^";n;"+$a+8"
 
 
 BEGIN:
 LOCATE 1,1:PRINT "10^";n;"+";Start
 
 REDIM F(96996900) AS BYTE  

 FOR zaehler=0 TO 9 // 10 mal 9699690 Block 
 
 FOR I=1 TO 36855  //Konstantes Feld Q - Feld für jeden Blockdurchlauf  in QC kopiert, weil im QC Feld  hier reduziert wird
 QC(I)=Q(I)
 NEXT I

 count=36855
 
 FOR i=1 TO 3000
 U=1
 XX=R(I)
 PP=P(i)
 
  
 WHILE u<count  // und das hier ist das Meisterstück ! REST (Primzahl bzgl Block ) MOD Primzahl
 soll hier 0,2,6, oder 8 sein, damit der 4er ungültig wird bei einer Bedingung 
 QZ=(QC(u) + XX ) MOD PP 
 IF QZ>8 THEN GOTO WEITER 
 IF QZ MOD 2 = 1 OR QZ=4 THEN GOTO WEITER // <10 und ungerade fallen auch raus
 QC(u)=QC(COUNT):COUNT-=1:u-=1 // Primärsieb ! Hole das letzte 4Tupel ins erste, wenn das 1. rausfällt, reduziere Anzahl der 4er im Block um 1
 WEITER:
 u+=1
 WEND
 
 R(I)=(R(I)+R2(I)) MOD PP // Errechne neuen Rest bei Blockverschiebung 9699690
 
  
 NEXT i
 
  
 

 // kopiere die übrigen in ein BYTE Feld der Größe 96996900 für weiteres Sieben, weil hier erstmals die 96996900 / Primteiler die Anzahl der Restkandidaten unterschreitet
F() ist das neue Siebfeld, der Endblock als Raster

 FOR j=1 TO count
    F(QC(j)+zaehler*9699690)=1
  F(QC(j)-2+zaehler*9699690)=1
  F(QC(j)-6+zaehler*9699690)=1
    F(QC(j)-8+zaehler*9699690)=1
 NEXT j
 

NEXT zaehler

// Siebe alle Primteiler ab der 3001. bis maxP wie gewohnt durch
 
 FOR i=3001 TO maxP
 U=1
 RR=P(i)-R(i)
 IF RR MOD 2= 0 THEN RR+=P(i)
 FOR j=RR TO 96996900 STEP P(i)*2
 F(j)=0
 NEXT j
 R(I)=(R(I)+R2(I)) MOD P(i)  // Auch hier die Restblock bzgl Primteiler bei Verschiebung Block 96996900
 
 NEXT i
 
 // Ausgabe aller übrigen 4er ab 41 in 30er Block aussuchen und in Datei fürs PRPing schreiben
 FOR i=41 TO 96996900 STEP 30
 IF F(i)=1 AND F(i+2)=1 AND F(i+6)=1 AND F(i+8 )=1 THEN PRINT #9,I+Start
 NEXT i
 
 
 STC=INT(Start/10^11)
 Start+=96996900
 IF START>ST THEN CLOSE #9:STOP
 // Prüft ob Datei abgeschlossen wird bei volle 100 Mrd
 IF INT(Start/10^11)>STC THEN CLOSE #9:GOTO B0
 
 GOTO BEGIN                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

procedure PrimSieben;
var
  i,p: NativeInt;
Begin
  fillchar(PrimSieb,SizeOf(PrimSieb),Ord(true));
  p := 2;
  repeat
    i := p*p;
    while i <= High(PrimSieb) do
    Begin
      PrimSieb[i] := false;
      inc(i,p);
    end;
    repeat
      inc(p);
    until PrimSieb[p]
  until (p*p) >High(PrimSieb);
end;                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

x                 Faktorisierung
1033669           7 13 37 307
8719309           19 37 79 157
9558334369        67 109 199 6577
107023329865      5 19 23 103 307 1549
317868427009      7 19 109 769 28513
1826363517265     5 7 53 79 157 163 487
2687463022465     5 13 17 19 67 1153 1657
3718714500865     5 7 13 19 397 769 1409
144692588218465   5 7 23 89 439 1237 3719
448933306317769   7 13 607 1213 6700249
637070091543865   5 7 107 397 8963 47807
842033901223945   5 53 109 313 937 99397
859152343812049   7 283 2179 7129 27919
1114610512354465  5 7 17 823 35117 64817
1206125685237889  13 59 73 929 1033 22447
2190392507242369  19 37 109 157 199 433 2113
4921398310999105  5 13 17 19 67 89 193 353 577
7248575534632705  5 7 13 17 37 97 433 523 1153
7459104727653085  5 13 37 67 199 277 829 1013                    

1:

9 16 53 81 100 107 144 173 256 363 374 381 386 417 456 465 477 517 534 545 ...                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:

Siebgroesse 2586584 Byte  // jedes Bit entspricht einem k aus 30*k+11-> 620.780.160
Start-Potenz  998
Start-Offset  0
//Zu Beginne werden alle Siebprimzahlen "ersiebt"
Anzahl Siebprimzahlen    98222284 bis 1999999973
//Die Anzahl der verwendeten Siebprimzahlen
Maximaler SiebprimIndex: 97930762  
//inclusive Primzahlen ersieben und Übertrag berechnen für SiebprimIndex
Siebzeit 00:00:21.674
Testzeit   00:00:18.886
Testzeit pro Kandidat 15.218 ms
Siebzeit 00:00:00.773
Testzeit   00:00:17.744
Testzeit pro Kandidat 14.961 ms
Siebzeit 00:00:00.771
Testzeit   00:00:16.967
Testzeit pro Kandidat 14.589 ms
Siebzeit 00:00:00.795
Testzeit   00:00:17.689
Testzeit pro Kandidat 14.231 ms  //Loesung gefunden, deshalb etwas weniger Zeit
  998  1970797081     00:01:35.309
Gesamtzeit: 00:01:35.310
----------
Start-Potenz  598
Start-Offset  0
Maximaler SiebprimIndex: 45959098
Siebzeit 00:00:04.617              //hier nur inclusive Übertrag berechnen für SiebprimIndex
Testzeit   00:00:04.902
Testzeit pro Kandidat  3.494 ms
Siebzeit 00:00:00.588
Testzeit   00:00:04.888
Testzeit pro Kandidat  3.409 ms
Siebzeit 00:00:00.596
Testzeit   00:00:04.954
Testzeit pro Kandidat  3.452 ms
Siebzeit 00:00:00.589
Testzeit   00:00:05.056
Testzeit pro Kandidat  3.451 ms
Siebzeit 00:00:00.587
Testzeit   00:00:04.622
Testzeit pro Kandidat  3.470 ms
Siebzeit 00:00:00.585
Testzeit   00:00:04.791
Testzeit pro Kandidat  3.417 ms
Siebzeit 00:00:00.583
Testzeit   00:00:04.730
Testzeit pro Kandidat  3.433 ms
Siebzeit 00:00:00.583
Testzeit   00:00:04.923
Testzeit pro Kandidat  3.435 ms
Siebzeit 00:00:00.585
Testzeit   00:00:04.949
Testzeit pro Kandidat  3.420 ms
Siebzeit 00:00:00.584
Testzeit   00:00:04.952
Testzeit pro Kandidat  3.441 ms
Siebzeit 00:00:00.584
Testzeit   00:00:00.050
Testzeit pro Kandidat  0.035 ms  //Loesung gefunden, deshalb weniger Zeit
  598  6011086471     00:00:59.367

Start-Potenz  430
Start-Offset  0
Maximaler SiebprimIndex: 28413753
Siebzeit 00:00:02.713
Testzeit   00:00:02.320
Testzeit pro Kandidat  1.456 ms
Siebzeit 00:00:00.504
Testzeit   00:00:02.337
Testzeit pro Kandidat  1.457 ms
Siebzeit 00:00:00.505
Testzeit   00:00:02.189
Testzeit pro Kandidat  1.416 ms
Siebzeit 00:00:00.504
Testzeit   00:00:02.340
Testzeit pro Kandidat  1.485 ms
Siebzeit 00:00:00.503
Testzeit   00:00:02.184
Testzeit pro Kandidat  1.418 ms
Siebzeit 00:00:00.502
Testzeit   00:00:02.262
Testzeit pro Kandidat  1.468 ms
Siebzeit 00:00:00.503
Testzeit   00:00:02.274
Testzeit pro Kandidat  1.421 ms
Siebzeit 00:00:00.513
Testzeit   00:00:02.339
Testzeit pro Kandidat  1.480 ms
Siebzeit 00:00:00.503
Testzeit   00:00:02.206
Testzeit pro Kandidat  1.424 ms
Siebzeit 00:00:00.502
Testzeit   00:00:02.370
Testzeit pro Kandidat  1.470 ms
Siebzeit 00:00:00.504
Testzeit   00:00:02.140
Testzeit pro Kandidat  1.427 ms
Siebzeit 00:00:00.503
Testzeit   00:00:01.572
Testzeit pro Kandidat  0.994 ms  //Loesung gefunden, deshalb weniger Zeit
  430  6969624301     00:00:34.836