xthexder

joined 1 year ago
[–] xthexder@programming.dev 1 points 1 year ago* (last edited 1 year ago) (1 children)

99.5% would still be e^200 numbers checked (7x10^86). According to the Quora link in my other comment, we've only calculated primes in sequence up to 4x10^18 as of 7 years ago. 95% is very doable though.

Edited to correct first N primes vs primes up to N.

[–] xthexder@programming.dev 2 points 1 year ago (3 children)

We got nerd sniped at almost the exact same time, but approached this in very different ways. I applaud your practical approach, but based on what I calculated, you should stop now. It will never reach 99.999%

[–] xthexder@programming.dev 37 points 1 year ago (1 children)

A few calculations:

  • There are 9592 prime numbers less than 100,000. Assuming the test suite only tests numbers 1-99999, the accuracy should actually be only 90.408%, not 95.121%
  • The 1 trillionth prime number is 29,996,224,275,833. This would mean even the first 29 trillion primes would only get you to 96.667% accuracy.
  • The density of primes can be approximated using the Prime Number Theorem: 1/ln(x). Solving 99.9995 = 100 - 100 / ln(x) for x gives e^200000 or 7.88 × 10^86858. In other words, the universe will end before any current computer could check that many numbers.
[–] xthexder@programming.dev 2 points 1 year ago

I got to this same result on my 3rd attempt, and had to throw in the towel. Everything's randomized every time.

[–] xthexder@programming.dev 9 points 1 year ago (2 children)

To be fair, I used to work there, and not even Microsoft understands their docs.