codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# 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 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): 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)
Private
[
?
]
Run code
Submit