Inhaltsverzeichnis

Development of
Algorithmic Constructions

english

The chance to find a big prime

If you sieve any target N to sufficient depth p and
and find that N still has no identified factor, then
the probability that N is prime is, heuristically:

P = exp(Euler)*log(p)/log(N)

where Euler = 0.577215664901532860606512090082402431...

Mertens, F. "Ein Beitrag zur analytischen Zahlentheorie."
J. reine angew. Math. 78, 46-62, 1874.



The "Sieving up to" bases on my own algorithm.

Digits Runtime Sieving up to Chance to find a prime
1000 < 1933 1 : 171
2000 0.1 sec < 4243 1 : 309
3000 0.3 sec < 6607 1 : 441
4000 0.6 sec < 8929 1 : 568
5000 1,2 sec < 11257 1 : 693
6000 1.8 sec < 13627 1 : 814
8000 3,6 sec < 18181 1 : 1054
10000 6,3 sec < 22861 1 : 1289
20000 34,0 sec < 46141 1 : 2408
30000 1,30 min < 69379 1 : 3480
40000 3 min < 92317 1 : 4524
50000 6 min < 115549 1 : 4631
60000 7,35 min < 138577 1 : 6553
80000 15 min < 184843 1 : 8531
100000 27 min < 230563 1 : 10471
200000 132 min < 461677 1 : 19828
1000000 < 2304553 1 : 88262
10000000 < 23035273 1 : 762769