Skip to main content
2 of 2
added 147 characters in body
dr jimbob
  • 358
  • 1
  • 6

Edward seemed to do a good job improving your code with your method of finding primes by checking divisibility by repeatedly dividing.

However, if your task is to quickly generate a list of primes in a large range, using a prime number sieve (e.g., Sieve of Eratosthenes or an optimized version like Sieve of Atkin or wheel sieves) is a better method.

Your method (as well as Edward's improvement by reducing redundant factors) takes \$O(N^{1.5})\$ to generate a list of primes from 1 to \$N\$ (\$\Sigma_{k=1}^{N} \sqrt{k} \sim O(N^{1.5}) \$). The Sieve of Eratosthenes takes \$O(N)\$ time to generate the primes from 1 to \$N\$ and the optimized variations are asymptotically faster and can take \$O(N/\log \log N)\$, though you should note for \$N = 2^{32} \sim 4 \;{\rm billion}\$ (common maximum value for an unsigned int), \$\log \log N = 5\$ and for \$N = 2^{64} \sim 10^{19}\$(common maximum value of an unsigned long long int), \$\log \log N = 6\$).

If you need to find larger primes (for example doing RSA and requiring 512-bit primes) or primes in a very small range, its probably better by first checking divisibility against a list of small primes (first 1000 primes or so) and then switch to a probabilistic primality test like Miller-Rabin or Baillie-PSW.

dr jimbob
  • 358
  • 1
  • 6