Skip to content

Instantly share code, notes, and snippets.

@SteadBytes
Created November 12, 2017 08:46
Show Gist options
  • Save SteadBytes/b3ba9f44b802b2ec150cdaa3d06850a6 to your computer and use it in GitHub Desktop.
Save SteadBytes/b3ba9f44b802b2ec150cdaa3d06850a6 to your computer and use it in GitHub Desktop.
Few methods for testing primality, with timing for comparison
import timeit
import math
def is_prime(n):
if n <=1:
return False
elif n <=3:
return True
elif n % 2 ==0 or n%3 == 0:
return False
i = 5
while i*i <= n:
if n%i == 0 or n%(i+2) == 0:
return False
i += 6
return True
def is_prime_2(n):
for i in range(2, int(math.sqrt(n))+1):
if n%i==0:
n = 1
if n ==1:
return False
return True
if __name__ == '__main__':
print('is_prime():')
print(timeit.timeit('is_prime(1000000007)',
setup='from __main__ import is_prime'))
print('is_prime_2():')
print(timeit.timeit('is_prime_2(1000000007)',
setup='from __main__ import is_prime_2'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment