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