Discussion :

[NVCfrm]

Eclairage sur les nombres premiers.

Bonjour.

---

Prelude
L'article suivant a été motivé par la discussion Code pour décomposer le nombre 52 ... en nombres premiers.
J'ai surtout été impressionné par la longueur du fil pour pas grand chose. Un don de Patrick.
Je me suis décidé aujourd'hui à chercher dans les foutoirs de code de mes archives à trouver quelque chose correspondant au besoin. Malheureusement ce que j'ai trouvé est en c. N'empêche que je l'ai adapté pour vba.
Ce fut pour moi aujourd'hui un rappel des recherches que j'ai eu à mener sur une implémentation par une formule magique de la chose sans succès.

Il y a beaucoup d'algos pour générer une suite de nombre premiers, il y a aussi beaucoup d'implémentations plus ou moins réussi de ces algos en informatique.
Tous les chemins menant à Rome, certains sont semés d'embûches parfois infranchissable est-on obligés de constater.

---

Détails Généraux à prendre en compte pour construire un algo

Premièrement tenir compte de quelques particularités des nombres.

• Un nombre premier est un nombre impair dont la division entière par tout autre que lui même ou 1 ne tombe pas., mais surtout est toujours Impair hormis le nombre 2.
• Un nombre impair supérieur à 10 non divisible par un nombres finissant par : 1 3, 5, 7, 9 est premier.
• Un nombre premier supérieur à 10, se termine toujours par 1, 3, 7, 9.
• Pour enfoncer le clou on énonce que le plus petit diviseur d'un nombre impair est premier, sinon ce nombre est un nombre premier. Soit e = 2 X N_i + 1 où i = 1 2 3 ..., si e est divisible 2 x N_i +1, alors 2 x N_i +1 est un nombre premier.
• Partant de ces principes, tout nombre supérieur à 10 se terminant par l'un des chiffres 1, 3, 7, 9 _
• peut être évalué dans une division par la série 3, 7, 9.
• Pourquoi ? Vous n'avez pas oublié que tout nombre qui se termine par 5 est _
• divisible par 5, que tout nombre divisé par 1 est égal à lui même.

On se demande donc comment trouver non nombres premiers ?
Dans les premiers nombres premiers pardi !
J'en vois qui sourcillent et disent "Quoi ?", ça ne dit pas d'où sort les premiers nombres premiers ?

Soit NB un nombre quelconque supérieur à 10 à examiner pour créer une liste de nombre premiers, T un tableau, n l'indice du dernier élément de T contenant un nombre premier, i une variable avec une limite de décalage sur NB', NB' un multiple de dix incrémenté par la liste des constantes 1, 3, 7, 9 devant être toujours inférieur ou égal à NB.

Si NB' % T_i != 0 alors T_n = NB'

Ça ne nous dit pas d'où le(s) premier's) T_n. Mouais. C'est à vous d'implémenter quelque chose qui crée T_n.

Voilà un exercice à ceux qui sont intéressés à trouver par eux même.
Les autres peuvent consulter l'exemple de code en pièce jointe.

Le code d'origine en C testé sur une vieille Dell Penthium4, 3.5Ghz donne les estimations de temps suivant :

00 100 000 9952 trouvés en 0.013492s
01 000 000 78498 trouvés en 0.25344s
10 000 000 664579 trouvés en 5.484s
8.000.000 donne 539777 en 3,895570s.


Le code en vb exécuté sur une XP virtualisé sur la même vieille Dell donne les estimations de temps suivant
pour 00 100 000 : 9592 nbp trouvés en 0,3828125s.
pour 01 000 000 78498 nbp trouvés en 7,9921875s.
pour 10 000 000 664579 nbp trouvés en 247,5546875s.

Edit : Ajout des fichiers de code.

[kiki29]

Salut, à titre indicatif : sur Wikipédia
plus spécialisés : Mersenne et calcul collaboratif parmi une myriade

[NVCfrm]

Merci infiniment pour ces liens. De l'autre côté Franck en a fait quelques implémentations réussies en vba.
De quoi réexaminer mes approches de la chose, des fois que j'aurais dû à perdre.

[NVCfrm]

J'aimerais que le moinseur silencieux dise ce qui le contrarie dans le ma réponse ci-dessus. Qu'on puisse dialoguer avec ses lumières qui pour l'instant sont bien obscures.
Habituellement ça n'éveille pas ma curiosité, sachant que je suis en face d'intervenants sur une position opposée.