Re:Code Llama, an AI tool for coding
by noduerme on Thursday August 24, 2023 @04:25PM
(#37254096)
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?
[ Parent
| on HN ]
Re:Code Llama, an AI tool for coding
by Our_Benefactors on Thursday August 24, 2023 @04:46PM
(#37254324)
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.
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 }
Re:Code Llama, an AI tool for coding
by thewataccount on Thursday August 24, 2023 @04:48PM
(#37254355)
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.
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
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
Re:Code Llama, an AI tool for coding
by bakuninsbart on Friday August 25, 2023 @09:50AM
(#37261719)
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.