# Is there a theoretical limit to how fast we can find prime numbers?

In other words:

• Given some positive integer $n$, is there a theoretical limit to how fast a computer with infinite computational power, memory, and storage, can find all the prime numbers below below $n$?

A similar question:

• Given some positive integer $n$, is there a theoretical limit to how fast a computer with infinite computational power, memory, and storage, can find whether or not $n$ is prime?
• en.wikipedia.org/wiki/AKS_primality_test. "Primes is in P" so you don't need that much time, even if your PC is "slow". – b00n heT Nov 9 '16 at 16:40
• Infinite computational power ? This would make the computer to an oracle, immediately finding the primes below $n$. – Peter Nov 9 '16 at 16:45
• @b00nheT Are you referring to $P$ as in $\mathrm{P} = \bigcup_{k\in\mathbb{N}} \mathrm{DTIME}(n^k)$? – Buffer Over Read Nov 9 '16 at 16:45
• @TheBitByte Yes, that's correct. – Noah Schweber Nov 9 '16 at 16:50

## 1 Answer

For simplification: Whenever I say number, I mean positive integer.

No, and your answers will have the same answer because finding all the prime numbers below n with require to check all numbers k, where k is every number less than n.

Theoretically, the brute-force method to checking primes (in this case, n or k) (which is generally never used in professional prime-finding) is to find two factors of the number by counting up from 2. If you reach n without finding any primes, then n is prime.

This requires arithmetic any computer can do at a rate exponentially proportional to its computational power, memory, and storage. Therefore, it can be modeled by a function, and as x approaches infinity, a polynomial equation with degree larger than 1 f(x) will approach infinity or negative infinity.

Basically a long way of saying no.

P.S. Unless you want me to be really nitpicky in which case I would ask about cooling systems, damage, and heat generated by computation, as well as outside influence and human error.

But ignoring all of those semi-avoidable things, no.