Skip to content

Instantly share code, notes, and snippets.

@kylieCat

kylieCat/fermat.py

Forked from bnlucas/fermat.py
Last active September 12, 2015 23:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kylieCat/03b3e1c568f4912cddc4 to your computer and use it in GitHub Desktop.
Save kylieCat/03b3e1c568f4912cddc4 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