2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random

def is_prime(n, k=5):
if n <= 1:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False

for i in range(k):
    a = random.randint(2, n-1)
    if pow(a, n-1, n) != 1:
        return False

return True