Algorithme de Carmichael

Le Carmichael :

"un entier positif composé n est un nombre de Carmichael si et seulement si aucun carré de nombre premier ne divise n (on dit que n est quadratfrei (sans carré)) et pour chaque diviseur premier p de n, le nombre p − 1 divise n − 1."

càd, qu'il s'exprime sous un produit de nombre premier à la puissance 1 (au moins 3 nombres premier différents)
-> tu peux donc partir d'un programme informatique qui va générer tous ces nombres possible, pui trier
-> le tri, il faut garder que ceux que pour "chaque diviseur premier p de n, le nombre p − 1 divise n − 1"

Merci beaucoup pascal16, et quel est l'énoncé de l'algorithme qui les-calculer en langage C.

si on prend les plus petits nombres premiers, le produit des 7 premiers font plus de 500 000.
limites-toi à 7 nombres premiers max.
j'ai lu (j'ai pas essayé de comprendre) qu'ils étaient multiples d'au moins 3 nombres premiers.
pour générer les 'candidats', il est facile de le faire en 5 boucles différentes, une qui ne génére que les candidats avec 3 diviseurs premiers, un pour 4 diviseurs premiers, etc.
Comme il a au moins 3 diviseurs premiers, il faut aller dans les nombres premiers jusqu'a : 1000 000/2/3 = 166 666 (tu peux aller moins loin pour les boucle à 4,5,6 ou 7 diviseurs).

Tu peux donc faire de 2 façon :
la façon crible de machin bidule : tu génère un liste de candidats en faisant toutes les combinaisons de nombres premiers de 3,4,5,6 ou 7 nombres premiers compris entres 2 et 166 666. Pris tu regardes ceux dons les diviseurs...
C'est long et lourd

Sinon, tu génères toutes les combinaison de nombres premiers de 2,3,4,5,6 ou 7 nombres premiers compris entre 2 et 166 666, et dès que tu en a généré un, tu vérifis s'il est bon ou pas, tu l'enregistres s'il est bon.

Au départ il faut d'abord générer un liste de nombres premiers

Merci bien.