Skip to main content
Code Review

Return to Answer

added 147 characters in body
Source Link
dr jimbob
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\$N\$ (\$\Sigma_{i=1}^{N} \sqrt{i} \sim O(N^{1.5}) \$\$\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\$N\$ and the optimized variations are asymptotically faster and can take \$O(N/\log \log N)\$, though you should note for N = 2^32 ~ 4 billion\$N = 2^{32} \sim 4 \;{\rm billion}\$ (common maximum sizevalue for an C unsigned int), log log N = 5\$\log \log N = 5\$ and for N = 2^64 \$N = 2^{64} \sim 10^{19}\$(common maximum sizevalue of an unsigned long long int), log log N = 6\$\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 to checkby first checking divisibility against a list of small primes (first 40001000 primes or so) and then switch to a probabilistic primality test like Miller-Rabin or Baillie-PSW.

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_{i=1}^{N} \sqrt{i} \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 ~ 4 billion (common maximum size for an C unsigned int), log log N = 5 and for N = 2^64 (common maximum size of an unsigned long long int), log log N = 6.

If you need to find larger primes (for example doing RSA), its probably better to check against a list of small primes (first 4000 primes or so) and then switch to primality test like Miller-Rabin or Baillie-PSW.

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.

Source Link
dr jimbob
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_{i=1}^{N} \sqrt{i} \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 ~ 4 billion (common maximum size for an C unsigned int), log log N = 5 and for N = 2^64 (common maximum size of an unsigned long long int), log log N = 6.

If you need to find larger primes (for example doing RSA), its probably better to check against a list of small primes (first 4000 primes or so) and then switch to primality test like Miller-Rabin or Baillie-PSW.