![Citation](https://forum.developpez.be/images/misc/quote_icon.png)
Envoyé par
sandaff
... Sachant que nous ne connaissons pas les facteurs premiers d'un nombre composé impair, comment peut on encadrer soit le plus petit diviseur ou le plus grand diviseur; soit le deux?
Il y a t-il de possibilité de faire ce calcul sur ce nombre composé et les valeurs qui encadre soit plus proche du diviseur? ...
La recherche des diviseurs éventuels d'un nombre impair (N) exige de passer par l'énumération des entiers impairs ne dépassant pas (√N); en l'absence de toute information sur le nombre de départ, il n'existe malheureusement pas de raccourci par cadrage des solutions recherchées.
On a par exemple:
# 1000000000000009 = 179*5586592178771 (l'identification du plus petit diviseur est alors très rapide);
# 1000000000000003 = 14902357 * 67103479 (les calculs sont alors 83000 fois plus longs):
# 1000000000000037 est premier (il faut donc effectuer plus de dix millions de vérifications).
La seule amélioration envisageable est d'utiliser une suite comportant une plus forte densité de termes premiers, par ex. la suite définie par
d MOD 30 = {1, 7, 11, 13, 17, 19, 23, 29 ...} , valable au-delà de 5 .
Le gain obtenu (8/30 = 27% de candidats à la primalité au lieu de 2/6 = 33%) se révèle décevant au regard de la complication de l'algorithme ... mais on aborde là un autre sujet de discussion.
Partager