0
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ 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". $\endgroup$ – b00n heT Nov 9 '16 at 16:40
  • $\begingroup$ Infinite computational power ? This would make the computer to an oracle, immediately finding the primes below $n$. $\endgroup$ – Peter Nov 9 '16 at 16:45
  • $\begingroup$ @b00nheT Are you referring to $P$ as in $\mathrm{P} = \bigcup_{k\in\mathbb{N}} \mathrm{DTIME}(n^k)$? $\endgroup$ – Buffer Over Read Nov 9 '16 at 16:45
  • 1
    $\begingroup$ @TheBitByte Yes, that's correct. $\endgroup$ – Noah Schweber Nov 9 '16 at 16:50
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.