Created
January 29, 2022 16:16
-
-
Save nicksspirit/b285e688b8a3f2235f5a2b1f52a75338 to your computer and use it in GitHub Desktop.
Naive Primality Test in python
This file contains hidden or 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
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