|
Question 902616: I am trying to run a program that tells me how many prime numbers there are in a range of numbers. I run it in intervals of 10,000 to 100,000. How long would the program take to determine all the prime numbers between 2 and the largest known primes (with about 13 million digits)
for 10,000 it took 0.494s
for 20,000 it took 1.100s
for 30,000 it took 1.965s
for 40,000 it took 3.149s
for 50,000 it took 4.579s
for 60,000 it took 6.305s
for 70,000 it took 8.108s
for 80,000 it took 10.343s
for 90,000 it took 12.560s
for 100,000 it took 15.091s
According to what I have now, How would I find the solution? I do understand that this will take a very long time, but how long exaclty
Found 2 solutions by richwmiller, richard1234:
Answer by richwmiller(17219)   (Show Source):
Answer by richard1234(7193)  (Show Source):
You can put this solution on YOUR website! That depends on the asymptotic runtime of your prime-checking algorithm, and you would also need a ton of space.
By the way, 15 seconds to check all primes up to 100000 seems pretty slow. I was able to create a list of primes up to 100000 in about 0.5 sec. Here is some example Python code:
def prime(n): #this one is on Wikipedia
___if n < 1: return False
___if not n%2 or not n%3: return False
___for i in xrange(5, int(n**0.5 + 1), 6):
______if not n%i or not n%(i+2): return False
___return True
Then to generate a list of primes:
def primeslist(n): #creates a list of primes <= n:
___l = []
___for i in range(1, n+1):
______if prime(i): l.append(i)
___return l
Of course there are faster methods but it only took 0.5 seconds to create the list.
|
|
|
| |
