# trouver un grand nombre premier

from random import *

n = int(input("Nombre de chiffres:"))
k = int(input("Nombre de tests:"))
p = 1-1/2**k

s = 0
nb_tirages = 0
while s == 0 and nb_tirages<1000:
    nb_tirages += 1
    N = 0
    while (N%10 in [0,2,4,5,6,8]) or sum(int(c) for c in str(N))%3 == 0:
        N = randint(10**(n-1),10**n-1)
    s = 1
    for i in range(k):
        A = randint(2,N-1)
        if pow(A,N-1,N) != 1:
            s = 0
            
print(N,f"est un nombre premier (avec probabilit� >= {p})")
print("Nombre de tirages n�cessaires:",nb_tirages)