Skip to main content
replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link

Your coding style is clean enough, although you could add longer more descriptive names, and use functions instead of doing everything at the top level. However your main issues are related to choice of algorithm for finding the prime numbers.

Your algorithm is currently to test whether it is dividable by all numbers below it self. And this you repeat for each new number. This is by far the most ineffective algorithm for finding primes, so here are some basic stuff to do better algorithms:

  • No need to check even numbers – Your loop could skip every even number since the division by 2 should eliminate all other even numbers...
  • No need to check beyond square root of \$n\$ – If none of the numbers below the square root divides it, then none above will divide it either. This makes sense as if it's not prime you'll have that \$a*b = n\$, and if \$a\$ is larger than the square root, \$b\$ has to be lower.
  • Avoid multiplies of 3's (as well as 2's) – Another optimization of the brute force is to change the incrementation from 2, as in the sequence: 5, 7, 9, 11, 13, 15, 17, 19, 21, ... One can see that to avoid the 3's (in bold) one adds +2, +4, +2, +4. This can be simplified to an initial value of increment = 2 and then let increment = 6 - increment.
  • Keep track of earlier primes – Finally, still using a naive approach, you should keep track of earlier primes, as for lower values testing for division against non-primes is also a waste of time.

However you should probably look into more efficient algorithms (see Wikipedia's Generating primes. One good candidate is the Sieve of Erasthones, i.e. like in this answerthis answer which has a cool animation as well.

Your coding style is clean enough, although you could add longer more descriptive names, and use functions instead of doing everything at the top level. However your main issues are related to choice of algorithm for finding the prime numbers.

Your algorithm is currently to test whether it is dividable by all numbers below it self. And this you repeat for each new number. This is by far the most ineffective algorithm for finding primes, so here are some basic stuff to do better algorithms:

  • No need to check even numbers – Your loop could skip every even number since the division by 2 should eliminate all other even numbers...
  • No need to check beyond square root of \$n\$ – If none of the numbers below the square root divides it, then none above will divide it either. This makes sense as if it's not prime you'll have that \$a*b = n\$, and if \$a\$ is larger than the square root, \$b\$ has to be lower.
  • Avoid multiplies of 3's (as well as 2's) – Another optimization of the brute force is to change the incrementation from 2, as in the sequence: 5, 7, 9, 11, 13, 15, 17, 19, 21, ... One can see that to avoid the 3's (in bold) one adds +2, +4, +2, +4. This can be simplified to an initial value of increment = 2 and then let increment = 6 - increment.
  • Keep track of earlier primes – Finally, still using a naive approach, you should keep track of earlier primes, as for lower values testing for division against non-primes is also a waste of time.

However you should probably look into more efficient algorithms (see Wikipedia's Generating primes. One good candidate is the Sieve of Erasthones, i.e. like in this answer which has a cool animation as well.

Your coding style is clean enough, although you could add longer more descriptive names, and use functions instead of doing everything at the top level. However your main issues are related to choice of algorithm for finding the prime numbers.

Your algorithm is currently to test whether it is dividable by all numbers below it self. And this you repeat for each new number. This is by far the most ineffective algorithm for finding primes, so here are some basic stuff to do better algorithms:

  • No need to check even numbers – Your loop could skip every even number since the division by 2 should eliminate all other even numbers...
  • No need to check beyond square root of \$n\$ – If none of the numbers below the square root divides it, then none above will divide it either. This makes sense as if it's not prime you'll have that \$a*b = n\$, and if \$a\$ is larger than the square root, \$b\$ has to be lower.
  • Avoid multiplies of 3's (as well as 2's) – Another optimization of the brute force is to change the incrementation from 2, as in the sequence: 5, 7, 9, 11, 13, 15, 17, 19, 21, ... One can see that to avoid the 3's (in bold) one adds +2, +4, +2, +4. This can be simplified to an initial value of increment = 2 and then let increment = 6 - increment.
  • Keep track of earlier primes – Finally, still using a naive approach, you should keep track of earlier primes, as for lower values testing for division against non-primes is also a waste of time.

However you should probably look into more efficient algorithms (see Wikipedia's Generating primes. One good candidate is the Sieve of Erasthones, i.e. like in this answer which has a cool animation as well.

Source Link
holroy
  • 11.5k
  • 1
  • 26
  • 59

Your coding style is clean enough, although you could add longer more descriptive names, and use functions instead of doing everything at the top level. However your main issues are related to choice of algorithm for finding the prime numbers.

Your algorithm is currently to test whether it is dividable by all numbers below it self. And this you repeat for each new number. This is by far the most ineffective algorithm for finding primes, so here are some basic stuff to do better algorithms:

  • No need to check even numbers – Your loop could skip every even number since the division by 2 should eliminate all other even numbers...
  • No need to check beyond square root of \$n\$ – If none of the numbers below the square root divides it, then none above will divide it either. This makes sense as if it's not prime you'll have that \$a*b = n\$, and if \$a\$ is larger than the square root, \$b\$ has to be lower.
  • Avoid multiplies of 3's (as well as 2's) – Another optimization of the brute force is to change the incrementation from 2, as in the sequence: 5, 7, 9, 11, 13, 15, 17, 19, 21, ... One can see that to avoid the 3's (in bold) one adds +2, +4, +2, +4. This can be simplified to an initial value of increment = 2 and then let increment = 6 - increment.
  • Keep track of earlier primes – Finally, still using a naive approach, you should keep track of earlier primes, as for lower values testing for division against non-primes is also a waste of time.

However you should probably look into more efficient algorithms (see Wikipedia's Generating primes. One good candidate is the Sieve of Erasthones, i.e. like in this answer which has a cool animation as well.