Nombres amisRésolu

Question

Bonjour tout le monde, Voila je débute en C, et pour un tp j'ai besoin de faire un programme qui m'affiche la liste des nombres amis inférieur ou égale à N telle que sommediviseur(a)=b et sommediviseur(b)=a. J'ai fais mon programme mais il ne m'affiche aucune résultats alors que je sais que 284 et 220 sont amis, voici mon programme, il est certainement très lourds, mais cela ne fais que deux semaines que j'ai débuter et que je ne fais que du C, donc je voudrais juste savoir ce qui cloche dans le programme merci : #include int sommediviseur(int n) { int diviseur,sommed; sommed=0; for(diviseur=1;diviseur<=n/2;diviseur=diviseur+1) { if(n%diviseur==0) { sommed=sommed+1; } } return sommed; } int main() { /* Affiche la liste des nombre amis 2 à 2 plus petit ou égale à A */ /*vérifiant (somme diviseur(nb1))= nb2 et vice -versa */ int nb1,nb2,A; printf("Donner un entier positif "); scanf("%d",&A); for(nb1=A;nb1>=2;nb1=nb1-1) { for(nb2=nb1-1;nb2>=1;nb2=nb2-1) { if((sommediviseur(nb1)==nb2) && (sommediviseur(nb2)==nb1)) { printf("les nombres %d et %d sont amis",nb1,nb2); } } } system("PAUSE"); } Merci d'avance Yann

mad_love_disease · Accepted Answer

Ton programme est bon, seulement tu ne calcules pas la bonne chose.

284 et 220 sont amis car:

les diviseurs de 284 sont: 1, 2, 4, 71 et 142 (somme=220)
les diviseurs de 220 sont 1, 2, 4,5, 10, 11, 20, 22, 44, 55, 110 (somme=284)

Regarde ce que te retourne ta fonction sommediviseur(in n) et tu comprendras pourquoi ca ne marche pas:

sommediviseur(284) va te renvoyer 5 au lieu de 220
sommediviseur(220) va te renvoyer 11 au de 284

Tu vois le truc??? ;)

 Mad_Love_Disease

Darksnakes · Answer

Ha oui, je vois mieux maintenant, je renvoyer le nombre de diviseur et non pas leur sommes, j'ai donc remplacé sommed=sommed+1 par sommed=sommed+diviseur, et ça marche de suite mieux.

Merci beaucoup pour la rapidité de la réponse, de totue façon je rsique de revenir pour d'autre problème un jour ou l'autre :-)

Encore merci

Yann

Darksnakes · Answer

Encore une question : je vois clairement que ma recherche sera longue, n'y aurait t'il pas un moyen d'optimiser mon programme simplement, par exemple pour la recherche des diviseurs , ou tout simplement pour la recherche des nombres

merci

Yann

Darksnakes · Answer

bon j'ai réécrit mon sous programme qui recherche les divisuer en allant jusqu'a la racine:

int sommediviseur(int n)
{
    int diviseur,sommed;
    sommed=1;
    for(diviseur=2;diviseur<=sqrt(n);diviseur=diviseur+1)
      {
       if(n%diviseur==0)
         {
          sommed=sommed+diviseur+n/diviseur;
          }
       }
     return sommed;
}    

Est ce que cette partie du programme peut encore être améliorer mathématiquement??

juki_webmaster · Answer

Salut,

for(diviseur=2;diviseur<=sqrt(n);diviseur=diviseur+1)
devient:
int s = sqrt(n);
or(diviseur=2;diviseur<=s;diviseur++)

sommed=sommed+diviseur+n/diviseur;
devient:
sommed+=diviseur+n/diviseur;

Pole4 · Answer

Il existe d'autres algorithmes de factorisation comme celui de rho
(inventé par Pollard) mais celui-là est suffisant pour les petits
nombres.

Pour le reste du programme, on peut aller bien plus vite en ne testant
que si sommediviseur(sommediviseur(a))==a, a et sommediviseur(a) seront
alors amis.


Pole.

Darksnakes · Answer

Le problème Pole c'est que, ce que tu me dit me fait afficher deux fois les même pairs, mais il est vrai que c'est beaucoup plus rapide. Comment je peux faire pour que ça ne m'affiche pas les deux fois la même paire?

Darksnakes · Answer

Bon ben pour le problème des deux pairs j'ai rajouté une condition, sinon grace a vous mon programme mets autant de temps pour afficher les nombres amis <= à 1000000 que l'ancien pour afficher les nombres amis <= à 10000. Le voici: #include int sommediviseur(int n) { int diviseur,sommed,s; s=sqrt(n); sommed=1; for(diviseur=2;diviseur<=s;++diviseur) { if(n%diviseur==0) { sommed+=diviseur+n/diviseur; } } return sommed; } int main() { /*Je fais le calcul pour tous les nombres compris entre 2 et A suivant le principe suivant */ /*2 nombres sont dis amis si sommediviseur(a)=b et si sommediviseur(b)=a*/ /*ce qui équivaut à sommediviseur(sommediviseur(a))=a alors */ /*sommediviseur(sommediviseur(a)) et a sont amis*/ int nb1,nb2,A; printf("Donner un entier positif "); scanf("%d",&A); for (nb1=A;nb1>=2;--nb1) { nb2=sommediviseur(nb1); if ((sommediviseur(nb2)==nb1) && (nb1A et les nombres parfaits*/ printf("les nombres %d et %d sont amis ",nb1,nb2); } } system("PAUSE"); } si vous avez d'autres conseils, je suis prenneur

Pole4 · Answer

Tu peux utiliser le crible d'Erathostène.
Dans un tableau de taille A, pour chaque nb < sqrt(A),tu parcours dans ton tableau par pas du nombre et tu ajoute ce nombre + l'index. A là fin, pour chaque nombre, tu as la somme des diviseurs.
int i,div1,div2;
for(i=0;i<=sqrt(A);i++){
div1=1,div2=i;
while(div2<A){tab[div2]+=div1+div2;div1++;div2+=i;}
}
Avec tab un tableau d'unsigned de taille A.
Tu n'as plus qu'à vérifier si tab[tab[i]]==i et si tab[i]<i. Attention, tab[i] peut être plus grand que A.

Pole.

Nombres amis

9 réponses

Votre réponse

Discussions similaires