Skip to content

Instantly share code, notes, and snippets.

@nicksspirit
Created January 29, 2022 16:16
Show Gist options
  • Save nicksspirit/b285e688b8a3f2235f5a2b1f52a75338 to your computer and use it in GitHub Desktop.
Save nicksspirit/b285e688b8a3f2235f5a2b1f52a75338 to your computer and use it in GitHub Desktop.
Naive Primality Test in python
import math
def smallest_div(n):
if n <= 1:
return 1
return min(i for i in range(2, n + 1) if n % i == 0)
def check_prime(n):
if n % 2 == 0:
return smallest_div(n)
r = math.sqrt(n)
i = 3
while i <= r:
if n % i == 0:
return smallest_div(n)
i += 2
return 1
def is_prime(n):
if n <= 1:
return smallest_div(n)
if n == 2:
return 1
return check_prime(abs(int(n)))
print(is_prime(4))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment