fork(2) download
copy 
  1. def is_prime(n):
  2.     if type(n) != int and type(n) != long:
  3.         raise TypeError('must be integer')
  4.     if n < 2:
  5.         return False
  6.     ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,
  7.          43,47,53,59,61,67,71,73,79,83,89,97]
  8.     def is_spsp(n, a):
  9.         d, s = n-1, 0
  10.         while d%2 == 0:
  11.             d /= 2; s += 1
  12.         t = pow(a,d,n)
  13.         if t == 1:
  14.             return True
  15.         while s > 0:
  16.             if t == n-1:
  17.                 return True
  18.             t = (t*t) % n
  19.             s -= 1
  20.         return False
  21.     if n in ps: return True
  22.     for p in ps:
  23.         if not is_spsp(n,p):
  24.             return False
  25.     return True
  26.  
  27. def rho_factors(n, limit=100):
  28.     if type(n) != int and type(n) != long:
  29.         raise TypeError('must be integer')
  30.     def gcd(a,b):
  31.         while b: a, b = b, a%b
  32.         return abs(a)
  33.     def rho_factor(n, c, limit):
  34.         f = lambda(x): (x*x+c) % n
  35.         t, h, d = 2, 2, 1
  36.         while d == 1:
  37.             if limit == 0:
  38.                 raise OverflowError('limit exceeded')
  39.             t = f(t); h = f(f(h)); d = gcd(t-h, n)
  40.         if d == n:
  41.             return rho_factor(n, c+1, limit)
  42.         if is_prime(d):
  43.             return d
  44.         return rho_factor(d, c+1, limit)
  45.     if -1 <= n <= 1: return [n]
  46.     if n < -1: return [-1] + rho_factors(-n, limit)
  47.     fs = []
  48.     while n % 2 == 0:
  49.         n = n // 2; fs = fs + [2]
  50.     if n == 1: return fs
  51.     while not is_prime(n):
  52.         f = rho_factor(n, 1, limit)
  53.         n = n / f
  54.         fs = fs + [f]
  55.     return sorted(fs + [n])
  56.  
  57. print rho_factors(99999640000243)
Success #stdin #stdout 0.11s 10864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[9999973L, 9999991L]
https://ideone.com/u9r6W
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!