My backwards logic

Seymore4Head Seymore4Head at Hotmail.invalid
Sat Sep 6 01:05:08 CEST 2014


On Fri, 5 Sep 2014 16:35:18 -0600, Ian Kelly <ian.g.kelly at gmail.com>
wrote:

>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.

That is a pretty nice example.
Thanks



More information about the Python-list mailing list