Blogdemaths - Le théorème de Wilson

#####################################################
# http://blogdemaths.wordpress.com
#
# Le théorème de Wilson - https://blogdemaths.wordpress.com/2015/10/26/le-theoreme-de-wilson/
#
######################################################

import math

def Divisions_naives(n):
''' Cette fonction renvoie True si n est premier. Elle est basée sur le constat suivant:
p est premier si, et seulement si, p n'est pas divisible par k pour tout k compris entre 1 et racine(p)'''

    if n==2:
        return True
    elif n%2==0:
        return False
    else:
        borne = int(math.sqrt(n))

        for k in range(3, borne+1, 2):
            if n%k==0:
                return False
        return True


def Wilson(n):
''' Cette fonction renvoie True si n est premier. Elle est basée sur le théorème de Wilson:
 p est premier si, et suelement si, (p-1)! = p-1 mod-p) '''

    if n==2:
        return True
    elif n%2==0:
        return False
    else:
        produit=1
        for k in range(2,n):
            produit = (produit*k)%n
        return produit == n-1