Closed spdskatr closed 7 years ago
There are only about 70,000 primes in this range, so a lookup table is kinda feasable. The primality checking in general is pretty crappy, has anyone actually tested to see how long it would take for noah's computer to check 999,983?
EDIT: proposal doesn't work, only a full lookup table would lead to significant speedup
On mediocre hardware, 10**10
will execute in around 0.3175048660126221
seconds. Upping it to 10**11
will take it to 1.0105299202432678
s, but I think 10**6
is probably a bit too small as that can easily execute in 0.0027852597500475137
s
Botter, do you actually understand how primes work?
Those numbers are basically best case scenarios. They get caught in the fist n%2 check and get passed. This is why I suggested 999983 as a test case, as it's worse case (and more representative of larger numbers)
Heh.. Derp..
999983
still had an average of 0.00011714474831082188
seconds. Oh, and those other numbers were wrong because they were the totals for all of the iterations not the average (because timeit
is that good).
I forget how fast modern computers are, I suppose we could go to 10**7 but I'd rather stay in the range of integers.
After a bit of testing the prime number 1000000005721 yielded 0.47870827575113567 seconds
made changes
oops