-
-
Save kylieCat/03b3e1c568f4912cddc4 to your computer and use it in GitHub Desktop.
Fermat primality testing with Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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