Maybe you underestimate how many numbers are weeded out just by checking divisibility by 3, 4 and 5? The first check regarding 2 will always return true, as `va

Maybe you underestimate how many numbers are weeded out just by checking divisibility by 3, 4 and 5? The first check regarding 2 will always return true, as `val` is incremented by 2. The check for divisibility by 3 will cause an abort for two out of three calls. The check for divisibility by 4 will cause an abort of half of the remaining calls (as `val` is incremented). And I guess the check for 5 will weed out an additional segment of 4 out 5. Thus just after checking 3, 4 and 5 only 1/3 * 1/2 * 1/5 of the `val`s will continue down the recursion call. So the majority of calls terminate in the highly optimized static division code. Now you can still argue that the remaining calls that go deep into the recursion could account for a lot of time. I don't believe this is the case though, as in each recursion call you should terminate a constant fraction of each calls, so the drop down should be exponential. An other interesting observation of this phenomenon is that running the recursion backwards (beginning with the large divisors) might greatly decrease the runtime as a more significant fraction of the `val`s are falsified by larger divisors in the first calls of the recursion.