1# Aim: Program to perform Miller-Rabin primality test (Miller-Rabin Primality Test).
2import random
3
4def miller_rabin(n,k=10):
5    if n in [2,3]:
6        return True
7    if n < 2 or n % 2 == 0:
8        return False
9    
10    r, d = 0, n-1
11    while d % 2 == 0:
12        r += 1
13        d //= 2
14    
15    for _ in range(k):
16        a = random.randint(2,n-2)
17        x = pow(a,d,n)
18        if x == 1 or x == n-1:
19            continue
20        for _ in range(r-1):
21            x = pow(x,2,n)
22            if x == n-1:
23                break
24        else:
25            return False
26    return True
27
28n=int(input("Enter a number to test for primality: "))
29if miller_rabin(n):
30    print(f"{n} is probably Prime")
31else:
32    print(f"{n} is Composite")