fork(13) download
  1. # prime power predicate
  2.  
  3. from random import randint
  4. from fractions import gcd
  5.  
  6. def findWitness(n, k=5): # miller-rabin
  7. s, d = 0, n-1
  8. while d % 2 == 0:
  9. s, d = s+1, d/2
  10. for i in range(k):
  11. a = randint(2, n-1)
  12. x = pow(a, d, n)
  13. if x == 1 or x == n-1: continue
  14. for r in range(1, s):
  15. x = (x * x) % n
  16. if x == 1: return a
  17. if x == n-1: break
  18. else: return a
  19. return 0
  20.  
  21. # returns p,k such that n=p**k, or 0,0
  22. # assumes n is an integer greater than 1
  23. def primePower(n):
  24. def checkP(n, p):
  25. k = 0
  26. while n > 1 and n % p == 0:
  27. n, k = n / p, k + 1
  28. if n == 1: return p, k
  29. else: return 0, 0
  30. if n % 2 == 0: return checkP(n, 2)
  31. q = n
  32. while True:
  33. a = findWitness(q)
  34. if a == 0: return checkP(n, q)
  35. d = gcd(pow(a,q,n)-a, q)
  36. if d == 1 or d == q: return 0, 0
  37. q = d
  38.  
  39. print primePower(1940255363782247**37)
Success #stdin #stdout 0.39s 10848KB
stdin
Standard input is empty
stdout
(1940255363782247L, 37)