| No it's not. It is only superficially[1]. The sieve of Eratosthenes goes like this: 1) Mark 2 as prime. Let it be n. 2) Mark all numbers of the form i times n as composite, where i
is a positive integer. (We can do this by stepping over multiples of n. No multiplication needs to take place. 3) The next unmarked number is prime. Let it be n. Goto 2 Notice how this alogorithm does not use division. Division in modern CPUs is slow. The algorithm presented uses the `mod` operator, which does division. This algorithm is equivalent to the Trial Division Algorithm. Instead of "deleting" multiples of n as composite, this algorithm tests all numbers greater than n for divisibilty by n, and then only does it "delete" the number. For a more detailed explanation, see http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf [1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Trial_di... |