a better prime number generator

Emile van Sebille emile at fenx.com
Sun Oct 21 20:47:22 CEST 2001


Hi Rupendra,

Without commenting on speed of your algorithm, you may want to compare to
the primes.py distributed in the demo/scripts directory of the cvs version:

---------primes.py--------
#! /usr/bin/env python

# Print prime numbers in a given range

def main():
    import sys
    min, max = 2, 0x7fffffff
    if sys.argv[1:]:
        min = int(eval(sys.argv[1]))
        if sys.argv[2:]:
            max = int(eval(sys.argv[2]))
    primes(min, max)

def primes(min, max):
    if 2 >= min: print 2
    primes = [2]
    i = 3
    while i <= max:
        for p in primes:
            if i%p == 0 or p*p > i: break
        if i%p <> 0:
            primes.append(i)
            if i >= min: print i
        i = i+2

main()
--------------------

Another note:  you should use spaces for indentation when posting.  Some
readers (mine included) lose the tabs which forces anyone looking at the
code to re-indent, sometimes introducing other bugs.  Bottom line is that
more people will look closer at your code fragments if they look like they
can be run.

HTH,

--

Emile van Sebille
emile at fenx.com

---------
"Rupendra Dhillon" <dhillon_rs at rediffmail.com> wrote in message
news:23d58b26.0110210939.55bb7e0c at posting.google.com...
> hi all,
> I have just been introduced to pyton and find it a very good ( takes
> off all the bookwork ) language. I was trying to develope a ast prime
> number generator. I designed the following algo. Can you please
> suggest a faster one or modifications to this only to make it faster
>
> #the following algo returns all the primes below x
>
> def getPrimesTill(x):
> a = range(2,x)
> c = [2]
>
> i = 0
> j = 0
>
> foundone = 1
>
> while i < len(a):
> while j < len(c) and (c[j] < (.5 * a[i]) ) and foundone == 1:
> if a[i]%c[j] == 0:
> foundone = 0
> j = j + 1
> if foundone == 1 and i > 0:
> c.append(a[i])
> j = 0
> foundone = 1
> i = i + 1
> return c
>
>
> roop




More information about the Python-list mailing list