not_IOFeb 22

o(1) statistical prime approximation

https://lemmy.blahaj.zone/post/38950495

Blåhaj Lemmy - Choose Your Interface

Show threadJustARegularNerd

I’m struggling to follow the code here. I’m guessing it’s C++ (which I’m very unfamiliar with)

bool is_prime(int x) { return false; }

Wouldn’t this just always return false regardless of x (which I presume is half the joke)? Why is it that when it’s tested up to 99999, it has a roughly 95% success rate then?

Feb 22 at 12:28pmWeb
Show threadflamingo_pinyataFeb 22
That’s the joke. Stochastic means probabilistic. And this “algorithm” gives the correct answer for the vast majority of inputs
Show threadkraftpuddingFeb 22
I suppose because about 5% of numbers are actually prime numbers, so false is not the output an algorithm checking for prime numbers should return
Show threadJustARegularNerdFeb 22

Oh I’m with you, the tests are precalculated and expect a true to return on something like 99991, this function as expected returns false, which throws the test into a fail.

Thank you for that explanation

Show threadAgent641Feb 22
And the natural distribution of primes gets smaller as integer length increases
Show threadHexareiFeb 22
Because only 5% of those numbers are prime