Programming With Prime Numbers: Source Code In Python

```# Programming With Prime Numbers # http://programmingpraxis.files.wordpress.com/ # 2012/09/programmingwithprimenumbers.pdf```

``` def sieve(n):     b, p, ps = [True] * (n+1), 2, []     for p in xrange(2, n+1):         if b[p]:             ps.append(p)             for i in xrange(p, n+1, p):                 b[i] = False     return ps 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         t = pow(a,d,n)         if t == 1:             return True         while s > 0:             if t == n-1:                 return True             t = (t*t) % n             s -= 1         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, limit=1000000):     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 rho_factor(n, c, limit):         f = lambda(x): (x*x+c) % n         t, h, d = 2, 2, 1         while d == 1:             if limit == 0:                 raise OverflowError('limit exceeded')             t = f(t); h = f(f(h)); d = gcd(t-h, n)         if d == n:             return rho_factor(n, c+1, limit)         if is_prime(d):             return d         return rho_factor(d, c+1, limit)     if -1 <= n <= 1: return [n]     if n < -1: return [-1] + rho_factors(-n, limit)     fs = []     while n % 2 == 0:         n = n // 2; fs = fs + [2]     if n == 1: return fs     while not is_prime(n):         f = rho_factor(n, 1, limit)         n = n / f         fs = fs + [f]     return sorted(fs + [n]) ```

```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)```