def find_prime_near(x):
while True:
if is_prime(x):
return x
x = x + 1
Naive primality test
def is_prime(x):
for i in range(2, x):
if x % i == 0: return False
return True
Faster Primality Testing
probabalistic test
passes the test, p(x is composite) <= 2 -k
Fermat's Little Theorem:
if p is prime, 1 <= a < p => ap-1 = 1 mod p
