3 ms·

I'm mad at myself now that it has eaten 15 minutes of my time trying to come up with the right optimization. What's the trick? 2, +1, and then +2 from there on

I'm mad at myself now that it has eaten 15 minutes of my time trying to come up with the right optimization. What's the trick? 2, +1, and then +2 from there on seems obvious but once you get to 9 is it worth building a list of nonprimes to skip?

Our_Benefactors 3y ago
https://stackoverflow.com/a/54544012/1336678 https://stackoverflow.com/a/54544012/1336678 Common approach is to use square roots, this reduces the runtime. Recommend checking out project euler if you like solving hard math-code-o(n)-puzzles.
- noduerme 3y ago
  I didn't want to cheat by looking on S.O. but thanks ;) Yes it makes sense (in the GPT code) that you'd only go up to i * i ... although looking at pythonic while: statements is just gross to me in this context, it would feel a lot more readable to say, e.g. in PHP: for ($i=2;$i<sqrt($n);) { $i+=($i==2 ? 1 : 2); //although the first one should just be outside the loop }
thewataccount 3y ago
I think they're suggesting simply doing +2 +1 is not a good idea since ~half of all numbers are effectively non-prime simply by being even numbers. You can double the speed by using +2 without using any fancy tricks, just changing a single character.
- nojs 3y ago
  Well it doesn’t double the speed, since anything with a factor of 2 undergoes only one loop iteration inside is_prime. It basically just saves a function call
dahfizz 3y ago
There's lots of more advanced optimizations, which would be an interesting avenue for discussion in an interview, but the drain dead algorithm would just use +2 instead of +1
bakuninsbart 3y ago
Exactly, multiples of 2 can't be a prime, so skipping this saves a function call (that itself only does one comparison), so it is a very simple and relatively obvious optimization. But actually every multiple of a number per definition cannot be a prime, you can't just change the step size, but there are some nifty tricks to approach the problem from a different angle.

Our_Benefactors 3y ago

https://stackoverflow.com/a/54544012/1336678 https://stackoverflow.com/a/54544012/1336678 Common approach is to use square roots, this reduces the runtime. Recommend checking out project euler if you like solving hard math-code-o(n)-puzzles.

noduerme 3y ago
I didn't want to cheat by looking on S.O. but thanks ;) Yes it makes sense (in the GPT code) that you'd only go up to i * i ... although looking at pythonic while: statements is just gross to me in this context, it would feel a lot more readable to say, e.g. in PHP: for ($i=2;$i<sqrt($n);) { $i+=($i==2 ? 1 : 2); //although the first one should just be outside the loop }

thewataccount 3y ago

I think they're suggesting simply doing +2 +1 is not a good idea since ~half of all numbers are effectively non-prime simply by being even numbers. You can double the speed by using +2 without using any fancy tricks, just changing a single character.

nojs 3y ago
Well it doesn’t double the speed, since anything with a factor of 2 undergoes only one loop iteration inside is_prime. It basically just saves a function call

dahfizz 3y ago

There's lots of more advanced optimizations, which would be an interesting avenue for discussion in an interview, but the drain dead algorithm would just use +2 instead of +1

bakuninsbart 3y ago

Exactly, multiples of 2 can't be a prime, so skipping this saves a function call (that itself only does one comparison), so it is a very simple and relatively obvious optimization. But actually every multiple of a number per definition cannot be a prime, you can't just change the step size, but there are some nifty tricks to approach the problem from a different angle.