import timeit
def naive_prime(n):
is_prime = False
for i in range(2, floor(sqrt(n))):
if n % i == 0:
is_prime = False
break
if is_prime:
print N, "est premier."
else:
print N, "n'est pas premier."
def wilson_prime(n):
fact = 1
imax = n
middle = (imax - 1) // 2 + 1
for i in range(2, middle):
fact *= i
fact %= n
for i in range(middle, imax):
fact *= imax - i
fact %= n
if (fact + 1)%n == 0:
print N, "est premier."
else:
print N, "n'est pas premier."
def wilson_prime_bis(n):
if (factorial(n) + 1)%n == 0:
print N, "est premier."
else:
print N, "n'est pas premier."
N = 32452843
duration = -timeit.timeit()
naive_prime(N)
duration += timeit.timeit()
print "Durée =", duration
duration = -timeit.timeit()
wilson_prime(N)
duration += timeit.timeit()
print "Durée =", duration
duration = -timeit.timeit()
wilson_prime_bis(N)
duration += timeit.timeit()
print "Durée =", duration