Essai de divisions (ou divisions successives)

Le principe

Comme son nom l'indique, la méthode par "Essai de divisions" (ou plus connu en anglais sous le nom de "Trial division") permet de trouver un facteur d'un nombre entier donné en tentant de diviser ce nombre par tous les autres qui lui sont inférieurs.
Cette méthode est extrêmement simple (voir simpliste) pour trouver un facteur d'un nombre et ne nécessite pas de connaissances mathématiques complexes.
En fait cette méthode reprend mot pour mot la définition d'un nombre premier puisque qu'un nombre premier est un entier naturel qui ne se divise que par 1 et par lui-même, prouver qu'un nombre est premier nécessite donc de vérifier qu'aucun nombre ne le divise et inversement un nombre n'est pas premier (composite) si nous trouvons au moins un facteur.

Au niveau de la complexité, l'algorithme est dans le pire des cas en O(n) ou en O(sqrt(n)) après optimisation (nous verrons ça un peu plus bas). Cette complexité n'est pas franchement géniale lorsque nous comparons à d'autres algorithmes existants mais la méthode est intéressante car relativement rapide pour trouver les petits facteurs d'un nombre. Il faut noter également que cet algorithme est utilisable dans les 3 grandes familles de problèmes sur les nombres premiers, à savoir : le test de primalité, la factorisation et la recherche d'une liste de premiers alors que les autres algorithmes sont cantonnés dans leur spécialité (le crible d'Eratosthène ne permet pas de factoriser un nombre...).

Nous allons donc explorer cette méthode afin de trouver tous les nombres premiers jusqu'à une borne fixée N et comparer les temps obtenus avec le crible d'Eratosthène et le crible d'Atkin.
Si vous avez lu la page d'accueil vous connaissez déjà la réponse "de qui est le plus rapide", pour les autres je ne spoilierai pas l'article...
Mais nous pouvons commencer à réfléchir au résultat que va donner la méthode par Essai de divisions et se dire qu'elle paraît pas si mal puisque nous allons parcourir les nombres de 1 à N et nous allons trouver très rapidement les petits facteurs de ces nombres... Et ces nombres avec des petits facteurs "il y en a beaucoup" par exemple si nous prenons un nombre au hasard, il y a 1 chance sur 2 qu'il soit divisible par 2 (le plus petit facteur dans les entiers), 1 chance sur 3 d'être divisible par 3, etc...

Première implémentation

D'un point de vue algorithmique, il nous faut donc plusieurs choses :

• Un tableau de booléen de 2 à N permettant de savoir si un nombre est premier ou non.
• Une boucle parcourant les nombres de 1 à N dont nous allons appliquer le test des divisions successives.
• Une deuxième boucle imbriquée qui tente les divisions de ce nombre avec un autre compris de 1 à N.

Avant de se lancer dans l'implémentation de cet algorithme, nous allons commencer par faire des optimisations évidentes :
- Concernant la 1ere boucle, nous allons éviter de tester les nombres pairs ils sont trivialement non premiers puisque divisibles par 2. Pour cela le parcours de la 1ere boucle se fera avec un pas de 2.
- Concernant la 2eme optimisation, elle portera sur la 2eme boucle où nous allons faire les tests de division uniquement jusqu'à racine carrée. Pourquoi ? Parce que si un nombre n'est pas premier et donc composite, il peut s'écrire sous la forme n = p * q et forcement l'un des 2 facteurs p ou q est inférieur à racine carrée de n. Ci-dessous, voici 2 démonstrations très ressemblantes reposant sur un raisonnement par l'absurde et prouvant que l'un des 2 facteurs est inférieur à racine carrée de n.

• Supposons p > √n et q > √n
  Signifie que p * q > √n * √n or √n * √n = n
  Donc p * q > n d'où contradiction
• Supposons p > √n et q > √n
  Signifie qu'il existe deux nombres positifs x et y tel que p = x + √n et q = y + √n
  Si nous multiplions p par q nous avons p * q = n = (x + √n) * (y + √n) = xy + √n(x * y) + n
  C'est-à-dire : xy + √n(x * y) = 0
  Or tous les membres de cette équation sont positifs, nous ne pouvons obtenir 0 d'où contradiction

Bon ! Ne nous le cachons pas les résultats sont très mauvais pour l'instant puisque qu'en comparaison avec le crible d'Eratosthène nous sommes à 0.906 secondes contre 0.031 pour la 1ere implémentation non optimisée, soit 30 fois plus long ! Pire, j'ai arrêté le test sur un tir à 100 millions car la cpu de mon vieux AMD 3200+ 6 ans d'âge tournait un peu trop à mon goût...
Ok il est temps d'améliorer tout ça.

source

Deuxième implémentation

Pour améliorer les temps il faut absolument réussir à faire moins de division que la première implémentation et pour cela nous allons partir d'une constatation :
Admettons que nous souhaitons tester l'essai par division sur le chiffre 105 (3*5*7) nous voyons que "i%j==0" renverra vrai (car divisible) pour 3, pour 5, pour 7 mais aussi pour 15, pour 21 et pour 35.
Inversons le raisonnement, soit le nombre 437 (19*23). Nous voyons que ce nombre n'est pas divisible par 3 ni par 5 et ne le sera pas non plus par 15 (3*5).
Notre première implémentation de l'Essai de divisions nous montre que nous faisons trop de divisions car nous essayons de diviser un nombre X avec des nombres composites dont les constituants premiers ne sont pas divisibles avec ce nombre X. L'idéal pour résoudre ce problème serait de faire les divisions successives avec uniquement des nombres premiers...
Nous avons l'impression de tourner en rond puisque le programme sert justement à calculer ces nombres premiers mais en fait c'est possible (!) puisque nous sommes entrain de les calculer, nous allons utiliser ceux déjà découverts pour trouver les suivants. C'est un peu comme si on réinjectait un résultat pour découvrir le résultat final.

Enfin nous noterons que le tableau ne contient plus de booléens mais les nombres premiers eux-mêmes. Cela signifie que pour tailler ce tableau, nous devons connaitre le nombre de nombres premiers lorsque nous effectuons un test sur une valeur N et pour cela il existe le théorème des nombres premiers disant que Pi(N) s'approche de N / ln(N) lorsque N tend vers l'infini (Wikipedia : Théorème des nombres premiers). Ici nos tests sont de l'ordre de la centaine de millions, nous sommes très loin de l'infini :) et donc nous sommes obligés de mettre un petit delta correctif (1.1).

Effectivement nous avons gagné beaucoup de temps avec cette optimisation ! Mais nous sommes encore loin du crible d'Eratosthène... Essayons de faire mieux. source

Troisième implémentation

Pour optimiser l'algorithme, nous allons avoir la même approche que pour l'optimisation du crible d'Atkin, nous allons nous attaquer à un des opérateurs qui représente en informatique une opération couteuse en temps. Ici il s'agira de la racine carrée.

Si nous regardons les valeurs que prennent la partie entière de la racine carrée nous voyons qu'elles suivent la séquence : 3 3  4 4 4  5 5 5 5  6 6 6 6 6... et nous pouvons en déduire la règle "l’entier n représentant la partie entière de la racine carrée est répété n-1 fois".
Il est possible de trouver plus d'informations en faisant un tour sur Wikipedia à l'adresse suivante : Racine carrée / rubrique "Les racines carrées, approximations entières".

Petit à petit nous améliorions mais cette fois-ci nous arrivons à la limite de l'optimisation. source

En conclusion

Nous remarquons donc que nous sommes très loin du compte en utilisant l'Essai par division par rapport aux autres cribles puisque malgré 3 optimisations nous avons encore un ratio de 1 pour 11 avec un crible d'Eratosthène non optimisé. Nous n'avons même pas chatouillé les cribles...
Cette différence se situe au niveau de la philosophie de l'algo, celui-ci tente de déterminer la primalité de manière ponctuelle (ce nombre que je choisis est-il premier ou non ?) et nous devons donc parcourir tous les nombres de 1 à N pour lancer les divisions. En comparaison un crible prend tous les nombres pour appliquer "une fonction tami" dessus et en général cette fonction est suffisante si elle est appliquée de 1 à racine carrée de N.

Par contre cette méthode a certains avantages, comme expliqué au début de l'article elle est simple elle permet de trouver rapidement des petits facteurs, elle peut être utilisée pour le test de primalité, la factorisation et la recherche d'une liste de premiers. D'ailleurs concernant ce dernier point, l'algo est flexible au niveau des bornes de recherche puisque nous ne sommes pas obligés de commencer à 1 contrairement au crible d'Eratosthène et de Atkin.