Nombres premiers : les écarts entre les nombres...

[SPH]

Bonjour a tous,

je me replonge dans un theme qui me tiens a coeur : les nombres premiers.
Pour factoriser un grand nombre (123456789 au pif), je peux essayer de le diviser par 3, puis par 5, puis 7 et 9 et 11...
Mais j'ai cru comprendre que l'on peux l'attaquer grace aux ecarts entre les nombres premiers : 2,2,4,2,4,2,4,6,2...
Est ce vrai ? Et si oui, comment ca marche ?

Merci

[gg0]

Bonsoir.

Je n’ai jamais entendu parler de ça, d'autant que la répartition des nombres premiers étant irrégulière, les écarts aussi.

Cordialement.

[SPH]

Y a t'il une autre methode que le crible d'erathostene pour trouver les facteurs d'un grand nombre ? (je serais étonné que non)

[gg0]

Oui,

il existe différentes méthodes (Wikipédia doit bien en donner quelques unes). Aucune n'est vraiment utilisable pour de très grands nombres (disons 100 chiffres). Pour le petits nombres, comme celui que tu cites, le test de 2, 3 puis des 6n-1 et 6n+1 est déjà assez rapide.

Cordialement.

[A voir en vidéo sur Futura]

[SPH]

Oui,

il existe différentes méthodes (Wikipédia doit bien en donner quelques unes). Aucune n'est vraiment utilisable pour de très grands nombres (disons 100 chiffres). Pour le petits nombres, comme celui que tu cites, le test de 2, 3 puis des 6n-1 et 6n+1 est déjà assez rapide.

Cordialement.

Tiens donc ! Tu viens de me donner un truc que je ne savais pas : les 6n-1 et 6n+1. Tu me confirme que ces 2 nombres reveleront les facteurs d'un NP ?

[gg0]

C'est quand même assez élémentaire (*) que en dehors de 2 et 3, tous les nombres premiers sont de la forme 6n-1 et 6n+1 (attention, dans les 6n-1 il y a des tas de composés, idem pour 6n+1). 6 étant 2 fois trois, on peut généraliser avec 2, 3, 5 et des nombres de la forme 30 n-23, 30n-19, 30n -17, 30n-13, 30n-11, 30n-7, 30n -1 et 30 n+1; mais pour la programmation, ce n'est pas plus performant.

Cordialement.

(*) vouloir parler de nombres premiers sans apprendre les bases de l'arithmétique c'est idiot : Il y a déjà des millions de gens qui ont réfléchi à cette question, depuis 2300 ans qu'on en parle, et il y a des tas de résultats connus. Évite de réinventer l'eau chaude. Renseigne-toi.