fork download
copy 
  1. def sieve(n):
  2.     b, p, ps = [True] * (n+1), 2, []
  3.     for p in xrange(2, n+1):
  4.         if b[p]:
  5.             ps.append(p)
  6.             for i in xrange(p, n+1, p):
  7.                 b[i] = False
  8.     return ps
  9. def primes(n):
  10.     if type(n) != int and type(n) != long:
  11.         raise TypeError('must be integer')
  12.     if n < 2:
  13.         raise ValueError('must be greater than one')
  14.     m = (n-1) // 2
  15.     b = [True] * m
  16.     i, p, ps = 0, 3, [2]
  17.     while p*p < n:
  18.         if b[i]:
  19.             ps.append(p)
  20.             j = 2*i*i + 6*i + 3
  21.             while j < m:
  22.                 b[j] = False
  23.                 j = j + 2*i + 3
  24.         i += 1; p += 2
  25.     while i < m:
  26.         if b[i]:
  27.             ps.append(p)
  28.         i += 1; p += 2
  29.     return ps
  30.  
  31. def td_prime(n, limit=1000000):
  32.     if type(n) != int and type(n) != long:
  33.         raise TypeError('must be integer')
  34.     if n % 2 == 0:
  35.         return n == 2
  36.     d = 3
  37.     while d * d <= n:
  38.         if limit < d:
  39.             raise OverflowError('limit exceeded')
  40.         if n % d == 0:
  41.             return False
  42.         d += 2
  43.     return True
  44.  
  45. def td_factors(n, limit=1000000):
  46.     if type(n) != int and type(n) != long:
  47.         raise TypeError('must be integer')
  48.     fs = []
  49.     while n % 2 == 0:
  50.         fs += [2]
  51.         n /= 2
  52.     if n == 1:
  53.         return fs
  54.     f = 3
  55.     while f * f <= n:
  56.         if limit < f:
  57.             raise OverflowError('limit exceeded')
  58.         if n % f == 0:
  59.             fs += [f]
  60.             n /= f
  61.         else:
  62.             f += 2
  63.     return fs + [n]
  64.  
  65. def is_prime(n):
  66.     if type(n) != int and type(n) != long:
  67.         raise TypeError('must be integer')
  68.     if n < 2:
  69.         return False
  70.     ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,
  71.          43,47,53,59,61,67,71,73,79,83,89,97]
  72.     def is_spsp(n, a):
  73.         d, s = n-1, 0
  74.         while d%2 == 0:
  75.             d /= 2; s += 1
  76.         t = pow(a,d,n)
  77.         if t == 1:
  78.             return True
  79.         while s > 0:
  80.             if t == n-1:
  81.                 return True
  82.             t = (t*t) % n
  83.             s -= 1
  84.         return False
  85.     if n in ps: return True
  86.     for p in ps:
  87.         if not is_spsp(n,p):
  88.             return False
  89.     return True
  90.  
  91. def rho_factors(n, limit=1000000):
  92.     if type(n) != int and type(n) != long:
  93.         raise TypeError('must be integer')
  94.     def gcd(a,b):
  95.         while b: a, b = b, a%b
  96.         return abs(a)
  97.     def rho_factor(n, c, limit):
  98.         f = lambda(x): (x*x+c) % n
  99.         t, h, d = 2, 2, 1
  100.         while d == 1:
  101.             if limit == 0:
  102.                 raise OverflowError('limit exceeded')
  103.             t = f(t); h = f(f(h)); d = gcd(t-h, n)
  104.         if d == n:
  105.             return rho_factor(n, c+1, limit)
  106.         if is_prime(d):
  107.             return d
  108.         return rho_factor(d, c+1, limit)
  109.     if -1 <= n <= 1: return [n]
  110.     if n < -1: return [-1] + rho_factors(-n, limit)
  111.     fs = []
  112.     while n % 2 == 0:
  113.         n = n // 2; fs = fs + [2]
  114.     if n == 1: return fs
  115.     while not is_prime(n):
  116.         f = rho_factor(n, 1, limit)
  117.         n = n / f
  118.         fs = fs + [f]
  119.     return sorted(fs + [n])
  120.  
Success #stdin #stdout 0.08s 10864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JTh2dT
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!