Skip to content

Instantly share code, notes, and snippets.

@bnlucas

bnlucas/fermat.py

Last active September 9, 2018 13:53
Show Gist options
  • Star 9 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save bnlucas/5857437 to your computer and use it in GitHub Desktop.
Save bnlucas/5857437 to your computer and use it in GitHub Desktop.
Download ZIP
Fermat primality testing with Python.
Raw
fermat.py
def fermat(n):
if n == 2:
return True
if not n & 1:
return False
return pow(2, n-1, n) == 1
# benchmark of 10000 iterations of fermat(100**10-1); Which is not prime.
# 10000 calls, 21141 per second.
# 20006 function calls in 0.481 seconds
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment