Editing ray

Title / Description

Code
def miller_rabin_prime(n): """Implementation of the Miller-Rabin probalistic primality test. http://en.wikipedia.org/wiki/Miller-Rabin_primality_test""" if n % 2 and n > 3: # Odd number greater than 3 k = 3 # Decide accuracy of our test #write n - 1 as 2s*d with d odd by factoring powers of 2 from n - 1 n1, s, d = n - 1, 0, 0 while True: if not n1 % 2: s += 1 n1 //= 2 else: d = n1 break for _ in range(k): a = randint(2, n - 1) x = pow(a, d, n) if x not in (1, n - 1): for _ in range(s): x = pow(x, 2, n) if x == 1: return False elif x == n -1: break else: return False # n is probably prime return True else: # 2 or 3 are the only prime numbers that will fall in here. return n in (2, 3)

Author

Highlight as C C++ CSS Clojure Delphi ERb Groovy (beta) HAML HTML JSON Java JavaScript PHP Plain text Python Ruby SQL XML YAML diff code