CoCalc Shared Fileswilson_theorem_implemented.sagews
Author: Christophe BAL
Views : 9
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

32452843 n'est pas premier. Durée = 0.000894784927368 32452843 n'est pas premier. Durée = 0.0190200805664 32452843 n'est pas premier. Durée = -0.0121507644653