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

>>>

'''