Nombres amis [Résolu]

Messages postés
19
Date d'inscription
samedi 21 octobre 2006
Dernière intervention
14 mars 2007
- 21 oct. 2006 à 10:10 - Dernière réponse :
Messages postés
20
Date d'inscription
mardi 11 octobre 2005
Dernière intervention
13 mars 2007
- 22 oct. 2006 à 10:15
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 <stdio.h>


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\n");
    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
Afficher la suite 

Votre réponse

9 réponses

Meilleure réponse
Messages postés
64
Date d'inscription
lundi 20 octobre 2003
Dernière intervention
1 juillet 2010
- 21 oct. 2006 à 11:14
3
Merci
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

Merci mad_love_disease 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 88 internautes ce mois-ci

Commenter la réponse de mad_love_disease
Meilleure réponse
Messages postés
20
Date d'inscription
mardi 11 octobre 2005
Dernière intervention
13 mars 2007
- 21 oct. 2006 à 14:27
3
Merci
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.

Merci Pole4 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 88 internautes ce mois-ci

Commenter la réponse de Pole4
Messages postés
947
Date d'inscription
mercredi 19 novembre 2003
Dernière intervention
5 avril 2008
- 21 oct. 2006 à 14:24
1
Merci
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;
Commenter la réponse de juki_webmaster
Messages postés
19
Date d'inscription
samedi 21 octobre 2006
Dernière intervention
14 mars 2007
- 21 oct. 2006 à 11:19
0
Merci
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
Commenter la réponse de Darksnakes
Messages postés
19
Date d'inscription
samedi 21 octobre 2006
Dernière intervention
14 mars 2007
- 21 oct. 2006 à 11:25
0
Merci
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
Commenter la réponse de Darksnakes
Messages postés
19
Date d'inscription
samedi 21 octobre 2006
Dernière intervention
14 mars 2007
- 21 oct. 2006 à 14:06
0
Merci
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??
Commenter la réponse de Darksnakes
Messages postés
19
Date d'inscription
samedi 21 octobre 2006
Dernière intervention
14 mars 2007
- 21 oct. 2006 à 14:45
0
Merci
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?
Commenter la réponse de Darksnakes
Messages postés
19
Date d'inscription
samedi 21 octobre 2006
Dernière intervention
14 mars 2007
- 21 oct. 2006 à 15:20
0
Merci
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 <stdio.h>


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\n");
    scanf("%d",&A);
    for (nb1=A;nb1>=2;--nb1)                                          
        {
         nb2=sommediviseur(nb1);
         if ((sommediviseur(nb2)==nb1) && (nb1<nb2)&& (nb1<=A) && (nb2<=A) )/*J'empeche de m'afficher deux foix la même paire*/
            {                                                                                                                                  /*ainsi que les valeurs >A et les nombres parfaits*/
             printf("les nombres %d et %d sont amis\n",nb1,nb2);
            }
        }
          system("PAUSE");


si vous avez d'autres conseils, je suis prenneur
Commenter la réponse de Darksnakes
Messages postés
20
Date d'inscription
mardi 11 octobre 2005
Dernière intervention
13 mars 2007
- 22 oct. 2006 à 10:15
0
Merci
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.
Commenter la réponse de Pole4

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.