Algo Notes: Count Primes

Description of problem here

Supposedly an easy problem, for those unfamiliar with number theory just the base premise pushes one to research how to determine if a number if a prime. There are variety of solutions from large n optimized probabilistic approaches, to more heuristic. However whether n is a prime is just a subproblem here, while many of the latter heuristic approaches can be memorized and serve rather performantly, a more intuitive approach which addresses the problem itself is the Sieve of Eratosthenes.

The basic intuition behind the Sieve of Eratosthenes is that for multiple of a prime is not a prime. We use this by iterating over from 2 until n marking each (easily achieved through a secondary list or using a set) of its multiples as nonprime and incrementing our prime counter, unless the current number has already been marked as prime.

Implementing this algorithm is rather straightforward once you decide how to "mark" a int. However, no matter if the algorithm is right, sometimes large n's just take a long time. Running a python version on 1500000 takes around a second on LeetCode, violating the time limitation. Writing a basic C version, though, easily reduces this time to 16ms. Both are rather readability, so this becomes a question of computational performance vs intelligibility. While I highly doubt applying a probabilistic method will get python to perform as quickly as the Sieve of Eratosthenes in C, even if it were to, it'd be much more obscure for non-critical use optimizing for maintainability.

Update: several updates can be made to severely optimize the sieve such using a half sieve which involves iterating from 2 until the square root of n - 1, not n.

.back