- #1

- 62

- 0

This is a simple question which has probably already been solved by someone, but I couldn't find it in the research anywhere, so maybe somebody here can help.

First of all, say we have a program which uses a new algorithm that outputs the nth prime when you input n, I call it a prime generator. I don't (quite) have such a program, but say we did.

say you input 10000 and it gives you the 10000th prime

then you input 10001 and it gives you 10001th prime

then you input 10002 and it gives you 10002th prime

then you input 10003 and it gives you 10003th prime

It continues in like fashion until it finds all primes in a given range, each of which requires some time to compute.

now this program is racing against the fastest test program that we have so far, and this test program checks ALL ODD INTEGERS after the 9999th prime to SEE IF THEY ARE PRIME. After checking alot of composites, it finds the 10000th prime. then it checks more odds until it finds the 10001th prime. In like fashion it continues checking each odd until it finds all the primes in the given range.

My question is, how efficient must the first program be to surpass the second program in efficiency?

Obviously, this is a non-trivial question, because the generator doesn't need to test all of the composites in between each prime.

Thanks for the help.

Aaron