Algorithmes sur entiers

Algorithmes sur entiers

Créateur de livres
Ajouter cette page à votre livre

Créateur de livres
Retirer cette page de votre livre

Ceci est une ancienne révision du document !

La manipulation d'entiers fait l'objet de nombreuses applications en chimie, du fait que les atomes (et isotopes) comptent des nombres entiers de nucléons (nombre de masse), que les molécules (ou ions, complexes) sont constituées d'atomes individuels (cf. formules brutes, indices), que les stœchimétries des réactions impliquent le plus souvent des entiers, que des structures (hélices, cristaux,…) sont caractérisées par des rapports entiers,…

Cette page reprend quelques grands algorithmes classiques sur les nombres entiers, et introduit quelques algorithmes ayant des applications en chimie.

Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d'entiers (a,b) comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme d'Euclide décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul (observez bien ici !). Cela donne ceci en Python : <sxh python; title : pgcd.py> #!/usr/bin/env python # -*- coding: UTF-8 -*- def gcd(a, b):

  """Calculate the Greatest Common Divisor of a and b.

  Unless b==0, the result will have the same sign as b (so that when
  b is divided by it, the result comes out positive).
  """
  while b:
      a, b = b, a%b
  return a

n1=210 n2=126 print gcd(n1, n2) </sxh>

Si on dispose des décompositions en facteurs premiers d'un nombre entier, on peut aussi établir la valeur du PGCD en effectuant le produit de tous les facteurs communs.

Algorithme d'Euclide
http://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python
https://docs.python.org/dev/library/fractions.html#fractions.gcd (version incluse dans le langage)
http://en.literateprograms.org/Euclidean_algorithm_%28Python%29 (améliorable !)

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même) : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …

Pour lister les nombres premiers strictement inférieur à un nombre N donné, un algorithme naïf (appelés tests de primalité) consiste à considérer les naturels un par un, en essayant de le diviser par tous les nombres inférieurs à sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Voici une implémentation en Python de cette idée.

<sxh python; title : nombres_premiers-01.py> #!/usr/bin/env python # -*- coding: UTF-8 -*- “”“ Liste de nombres premiers strictement inférieurs à un entier donné ”“” def isprime(n):

  for x in range(2,int(n**0.5)+1):
      if n % x == 0:
          return False
  return True

def primelist(n):

  return [a for a in range(2,n) if isprime(a)]

p=primelist(1000) print p </sxh>

L'algorithme peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée. Le crible d'Ératosthène est une méthode, reposant sur cette idée, qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers. Voici une implémentation en Python du crible d'Ératosthène :

<sxh python; title : nombres_premiers-03.py> #!/usr/bin/env python # -*- coding: UTF-8 -*- “”“ Liste de nombres premiers strictement inférieurs à un entier donné ”“” def primelist(n):

  """
  Version avec crible d'Eratosthenes
  """
  li = range(n+1)  # création d'une liste d'entiers jusque n
  li[1] = 0        #  0 (déjà à 0) et 1 ne sont pas premiers
  ncur = 2            # prochain nombre à tester
  while ncur ** 2 <= n:  # tant que ncur est inférieur à sqrt(n)
      li[ncur*2::ncur] = [0] * (n // ncur - 1) # éliminer (mettre à 0)
                                        # les multiples de ncur
      # ncur suivant (il ne doit pas être déjà mis à zéro)
      ncur += 1
      while not li[ncur]:
          ncur += 1
  return [a for a in li if a != 0]  # renvoie une liste avec les élements non nuls

p=primelist(1000) print p </sxh>