SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ## lecon 13 arithmétique
  2.  
  3. ##-1 diviseurs, nombres premiers, factorisation(s)
  4.  
  5. #liste des diviseurs positifs
  6.  
  7. def diviseurs(x):
  8.     D=[]
  9.     dor d in range(1, x+1) :
  10.         if  x % d == 0:
  11.             D.append(d)
  12.     return D
  13.  
  14. # le mm en mieux
  15.  
  16. def diviseurs(x):
  17.     D=[]
  18.     d=1
  19.     while ... :
  20.         if x % d == 0 :
  21.             D.append(d)
  22.             D.append(x//d)
  23.         d+= 1
  24.     if d** 2 == x :
  25.         D.append(d)
  26.         return D
  27.  
  28. # Et pour les avoir dans l'ordre
  29.  
  30. def diviseurs(x):
  31.     LesPetits = []
  32.     LesGros = []
  33.     d = 1
  34.     while d** 2 < x :
  35.         if x % d == 0:
  36.             LesPetits.append(d)
  37.             LesGros.append(x//d)
  38.         d+= 1
  39.     if d** 2 == x:
  40.         LesPetits.append(d)
  41.     while LesGros != []:
  42.         LesPetits.append(Les.gros.pop())
  43.     return LesPetits
  44.    
  45. # produit des diviseurs
  46.  
  47. def ProduitDesDiviseurs(x):
  48.     D= diviseurs(x)
  49.     P=1
  50.     for d in D :
  51.         P*= d
  52.     return P
  53.    
  54. ## Nombres premiers
  55.  
  56. def EstPremier(x) :
  57.     if x< 2 :
  58.         return False
  59.     elif x % 2 == 0 :
  60.         return x == 2
  61.     else :
  62.         d= 3
  63.         while d**2 <= x :
  64.             if x% d== 0:
  65.                 return False
  66.             d+= 2
  67.         return True
  68.  
  69.  
  70. ## Plus petit diviseur (à partir de main)
  71.  
  72. # On suppose que x n'a aucun diviseur strictement inférieur à dmin
  73.  
  74. def PlusPetitDiviseur(x, dmin) :
  75.     d= dmin
  76.     while d**2<= x:
  77.         if x% d == 0:
  78.             return d
  79.         d+= 1
  80.     return x
  81.    
  82. # liste des facteurs premiers (avec répétitions)
  83. def FacteursPremiers(x):
  84.     dmin = 2 ; F = []; x_ = x
  85.     while x_ > 1 :
  86.         p= PlusPetitDiviseur(x_, dmin)
  87.         dmin = p ; F.append(p) ; x_ // =p
  88.     return F
  89.  
  90. # valuation de p dans x : c'est le plus grand entier v tel que p**v divise x.
  91.  
  92. def Valuation(p,x):
  93.     v= 0
  94.     while x % p** (v + 1) ==0 :
  95.         v += 1
  96.     return v
  97.    
  98. # variante plus efficace
  99.  
  100. def Valuation(p, x):
  101.     v= 0; x_=x
  102.     while x_% p == 0 :
  103.         v+= 1 , x_ //= p
  104.     return v
  105.    
  106. # factorisation sous forme compacte
  107. def Facttorisation(x):
  108.     dmin = 2 ; F = [] ; x_ = x
  109.     while x_ > 1:
  110.         p = PlusPetitDiviseur(x_, dmin)
  111.         v = Valuation(p,x_)
  112.         dmin = p + 1 ; F.append( (p,v)) ;x_//=p **v
  113.     return F
  114.  
  115. ## tous les nb premiers: le crible d'érathostène
  116.  
  117. """
  118. on construit une liste B de booléens, indicée de 0 jusqu'à M, et on fait en sorte que la case B[x] soit vraie si et seulement si x est prmier .
  119. """
  120.    
  121. def erathosthène(M):
  122.     B=[True]*(M+1)
  123.     B[0] = False ; B[1] = False
  124.     d= 2
  125.     while d**2 <= M:
  126.         m = d*2
  127.         while  m<M :
  128.             B[m] = False
  129.             m+= d
  130.         d+= 1
  131.         while d**2 <= M and not B[d] :
  132.             d+= 1
  133.     P= []
  134.     for x in range(0, M+1):
  135.         if B[x]:
  136.             P.append(x)
  137.        
  138.     return P
  139.    
  140. ## 2 - L'algo d'Euclide
  141.  
  142. def PGCD(x, y):
  143.     x_= abs(x) ;y_=abs(y)
  144.     while y_> 0:
  145.         (x_, y_)=(y_, x_ % )
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top