My backwards logic

[Ian Kelly]

On Fri, Sep 5, 2014 at 3:49 PM, Seymore4Head
<Seymore4Head at hotmail.invalid> wrote:
> I am sure this has already been done, but after it was pointed out
> that you don't need to test for any number that multiplies by 2 it
> made me think again.
>
> If you start with the list [3,5,7] and step through the list of all
> remaining odd numbers (step 2), and start appending numbers that won't
> divide by numbers already appended in the list, that would seem like a
> pretty efficient way to find all prime numbers.

Indeed, this type of algorithm is known as a sieve. For a (literally)
classical example, see
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

It's a nice way to find all the prime numbers up to a given limit, or
it can be modified to run indefinitely high, but it's not very
efficient for determining the primality of a single number.