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?
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.