Back to SDS/2 Parametric Scripts

 

 

def prime(u):

    outList = range(3,u+1, 2)

    for i in xrange(3,u+1, 2):

        s = int(i**0.5)+1

        for n in xrange(2, s):

            if i%n == 0:

                outList[(i-3)/2] = 0

                break

    return [2]+[item for item in outList if item]

 

# This is about 80% faster than prime()

def prime1(u):

    outList = [2]

    for i in xrange(3, u+1, 2):

        p = True

        s = int(i**0.5)+1

        for n in xrange(3, s, 2):

            if i%n == 0:

                p = False

                break

        if p: outList.append(i)

    return outList

 

''' slightly slower

def prime1(u):

    a = range(2, int(u**0.5))

    outList = range(2,u+1)

    for i in outList[:]:

        for n in a:

            if i%n == 0 and n < i:

                outList[i-2] = 0

                break

    return [item for item in outList if item]

'''

 

''' about 100x slower

def prime1(u):

    ul = int(u**0.5)+1

    outList = range(2,u+1)

    for i in range(2,u+1):

        for n in range(2,max(i,ul)):

            if i != n and i%n == 0:

                outList[i-2] = 0

                break

    return [x for x in outList if x]

'''

 

def primes(low, high):

    outList = [i for i in range(low,high+1) if i%2 != 0 and i%3 != 0]

    if low == 3:

        outList = [3]+outList

    elif low == 2:

        outList = [2,3]+outList

    for i, item in enumerate(outList):

        s = int(item**0.5)+1

        for n in xrange(2, s):

            if item%n == 0:

                outList[i] = 0

                break

    return [x for x in outList if x]

 

# print ', '.join([str(x) for x in primes(2, 200)])

 

'''

>>> 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, \

71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, \

151,157, 163, 167, 173, 179, 181, 191, 193, 197, 199

'''

 

def large_primes(low, high):

    if high <= low:

        raise ValueError, 'Argument #2 must be greater than argument #1'

    elif (high-low) > 30000:

        raise ValueError, 'The difference between argument #2 and argument #1 must be less than 30001'

    pList = primes(2,200)

    numList = range(low, high)

    lpList = range(low, high)

    for num in numList:

        for p in pList:

            if num % p == 0:

                lpList.remove(num)

                break

    for num in lpList[:]:

        for i in xrange(9, int(high**0.5+1), 2):

            if num % i == 0:

                lpList.remove(num)

                break

    return lpList

 

def is_prime(n):

    count = 2

    while count < n**0.5:

        if n % count == 0:

            print '%d is a product of %d and %d' % (n, count, n/count)

            return False

        count += 1

    #print n, 'is a prime number'

    return True

 

 

if __name__ == '__main__':

    import timeit

    t = timeit.Timer("prime(300000)", "from __main__ import prime")

    print t.timeit(1)

    t = timeit.Timer("prime1(300000)", "from __main__ import prime1")

    print t.timeit(1)

   

    t = timeit.Timer("primes(2,300000)", "from __main__ import primes")

    print t.timeit(1)'''

 

>>> 4.42306159023

4.55718087075

0.047195942501

0.0151619828777

>>>

'''

 

    pList = large_primes(20000000000, 20000001000)

    print ', '.join([str(x) for x in pList])

    for p in pList:

        is_prime(p)

'''

>>> 20000000089, 20000000113, 20000000117, 20000000179, 20000000201, 20000000219, 20000000227, 20000000231, 20000000281, 20000000291, 20000000299, 20000000333, 20000000357, 20000000369, 20000000401, 20000000431, 20000000467, 20000000473, 20000000479, 20000000549, 20000000561, 20000000593, 20000000611, 20000000687, 20000000711, 20000000719, 20000000731, 20000000737, 20000000747, 20000000789, 20000000803, 20000000809, 20000000821, 20000000869, 20000000873, 20000000893, 20000000903, 20000000927

20000000089 is a prime number

20000000113 is a prime number

20000000117 is a prime number

20000000179 is a prime number

20000000201 is a prime number

20000000219 is a prime number

20000000227 is a prime number

20000000231 is a prime number

20000000281 is a prime number

20000000291 is a prime number

20000000299 is a prime number

20000000333 is a prime number

20000000357 is a prime number

20000000369 is a prime number

20000000401 is a prime number

20000000431 is a prime number

20000000467 is a prime number

20000000473 is a prime number

20000000479 is a prime number

20000000549 is a prime number

20000000561 is a prime number

20000000593 is a prime number

20000000611 is a prime number

20000000687 is a prime number

20000000711 is a prime number

20000000719 is a prime number

20000000731 is a prime number

20000000737 is a prime number

20000000747 is a prime number

20000000789 is a prime number

20000000803 is a prime number

20000000809 is a prime number

20000000821 is a prime number

20000000869 is a prime number

20000000873 is a prime number

20000000893 is a prime number

20000000903 is a prime number

20000000927 is a prime number

>>>

>>> is_prime(4638767895777)

4638767895777 is a product of 3 and 1546255965259

False

>>> is_prime(4638767895781)

4638767895781 is a prime number

True

>>> large_primes(4638767895770, 4638767895790)

[4638767895781L]

>>> is_prime(4638767895783)

4638767895783 is a product of 3 and 1546255965261

False

>>> is_prime(4638767895787)

4638767895787 is a product of 82339 and 56337433

False

>>>

'''