Blogdemaths

Blogdemaths - Le théorème de Wilson

Oct 26th, 2015
341
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #####################################################
  2. # http://blogdemaths.wordpress.com
  3. #
  4. # Le théorème de Wilson - https://blogdemaths.wordpress.com/2015/10/26/le-theoreme-de-wilson/
  5. #
  6. ######################################################
  7.  
  8. import math
  9.  
  10. def Divisions_naives(n):
  11. ''' Cette fonction renvoie True si n est premier. Elle est basée sur le constat suivant:
  12. p est premier si, et seulement si, p n'est pas divisible par k pour tout k compris entre 1 et racine(p)'''
  13.  
  14.     if n==2:
  15.         return True
  16.     elif n%2==0:
  17.         return False
  18.     else:
  19.         borne = int(math.sqrt(n))
  20.  
  21.         for k in range(3, borne+1, 2):
  22.             if n%k==0:
  23.                 return False
  24.         return True
  25.  
  26.  
  27. def Wilson(n):
  28. ''' Cette fonction renvoie True si n est premier. Elle est basée sur le théorème de Wilson:
  29. p est premier si, et suelement si, (p-1)! = p-1 mod-p) '''
  30.  
  31.     if n==2:
  32.         return True  
  33.     elif n%2==0:
  34.         return False
  35.     else:
  36.         produit=1
  37.         for k in range(2,n):
  38.             produit = (produit*k)%n
  39.         return produit == n-1
RAW Paste Data