Project:
programmingpraxis
programmingpraxis
-
Python,
pasted
on Apr 5:
|
# programming with prime numbers
def primes(n):
if type(n) != int and type(n) != long:
raise TypeError('must be integer')
if n < 2:
raise ValueError('must be greater than one')
m = (n-1) // 2
b = [True] * m
i, p, ps = 0, 3, [2]
while p*p < n:
if b[i]:
ps.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i += 1; p += 2
while i < m:
if b[i]:
ps.append(p)
i += 1; p += 2
return ps
def td_prime(n, limit=1000000):
if type(n) != int and type(n) != long:
raise TypeError('must be integer')
if n % 2 == 0:
return n == 2
d = 3
while d * d <= n:
if limit < d:
raise OverflowError('limit exceeded')
if n % d == 0:
return False
d += 2
return True
def td_factors(n, limit=1000000):
if type(n) != int and type(n) != long:
raise TypeError('must be integer')
fs = []
while n % 2 == 0:
fs += [2]
n /= 2
if n == 1:
return fs
f = 3
while f * f <= n:
if limit < f:
raise OverflowError('limit exceeded')
if n % f == 0:
fs += [f]
n /= f
else:
f += 2
return fs + [n]
def is_prime(n):
if type(n) != int and type(n) != long:
raise TypeError('must be integer')
if n < 2:
return False
ps = [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]
def is_spsp(n, a):
d, s = n-1, 0
while d%2 == 0:
d /= 2; s += 1
if pow(a,d,n) == 1:
return True
for r in xrange(s):
if pow(a, d*pow(2,r), n) == n-1:
return True
return False
if n in ps: return True
for p in ps:
if not is_spsp(n,p):
return False
return True
def rho_factors(n):
if type(n) != int and type(n) != long:
raise TypeError('must be integer')
def gcd(a,b):
while b: a, b = b, a%b
return abs(a)
def facts(n,c,fs):
f = lambda(x): (x*x+c) % n
if is_prime(n): return fs+[n]
t, h, d = 2, 2, 1
while d == 1:
t = f(t); h = f(f(h))
d = gcd(t-h, n)
if d == n:
return facts(n, c+1, fs)
if is_prime(d):
return facts(n//d, c+1, fs+[d])
return facts(n, c+1, fs)
if -1 <= n <= 1: return [n]
if n < -1: return [-1] + rho_factors(-n)
fs = []
while n%2 == 0:
n = n//2; fs = fs+[2]
if n == 1: return fs
return sorted(facts(n,1,fs))
print primes(100)
print len(primes(1000000))
print td_prime(600851475143)
print td_factors(600851475143)
print is_prime(600851475143)
print is_prime(2305843009213693951)
print rho_factors(600851475143)
|
Output:
|
[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]
78498
False
[71, 839, 1471, 6857L]
False
True
[71L, 839L, 1471L, 6857L]
|
|