CoCalc Shared Fileswilson_theorem_implemented.sagewsOpen in CoCalc with one click!
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