Project:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 ``` ```# 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) ```
 ```1 2 3 4 5 6 7 ``` ```[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] ```