Skip to main content
Code Golf

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

3
  • \$\begingroup\$ You only need to test primes up to the square root of the input. Once you've tested the small primes and the square of the next prime to be tested is bigger than the input, you can skip to the end. \$\endgroup\$ Commented Jan 7, 2022 at 20:19
  • \$\begingroup\$ @LevelRiverSt I actually thought about that a while after I posted this. That's exactly why there is a bit leap in CPU time going from 200 million to 300 million (the tests happen at 9, 121, 16129, 260467321). On real CPU, adding the test every line gained a lot in the higher ranges but was slower in the lower ranges. I didn't test what works better on this VM, but I just guessed maybe the increased code size won't pay off because the given range is only up to 2 million. \$\endgroup\$ Commented Jan 8, 2022 at 0:54
  • 1
    \$\begingroup\$ Sorry I didn't realise you already had some tests in there. I figured you wouldn't want to do the input size test every time. I would have thought the optimum would be somewhere in the range of one input size test per every 5 to 10 trial divisions. I doubt the test at 9 is doing anything for you. I would say get rid of that, and add several more at higher values. \$\endgroup\$ Commented Jan 8, 2022 at 1:13