# Development ofAlgorithmic Constructions

### 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