Nombres amis [Résolu]

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

9 réponses

Répondre au sujet
mad_love_disease 64 Messages postés lundi 20 octobre 2003Date d'inscription 1 juillet 2010 Dernière intervention - 21 oct. 2006 à 11:14
+3
Utile
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
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de mad_love_disease
juki_webmaster 947 Messages postés mercredi 19 novembre 2003Date d'inscription 5 avril 2008 Dernière intervention - 21 oct. 2006 à 14:24
+3
Utile
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;
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de juki_webmaster
Pole4 20 Messages postés mardi 11 octobre 2005Date d'inscription 13 mars 2007 Dernière intervention - 21 oct. 2006 à 14:27
+3
Utile
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.
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de Pole4
Darksnakes 19 Messages postés samedi 21 octobre 2006Date d'inscription 14 mars 2007 Dernière intervention - 21 oct. 2006 à 11:19
0
Utile
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
Darksnakes 19 Messages postés samedi 21 octobre 2006Date d'inscription 14 mars 2007 Dernière intervention - 21 oct. 2006 à 11:25
0
Utile
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
Darksnakes 19 Messages postés samedi 21 octobre 2006Date d'inscription 14 mars 2007 Dernière intervention - 21 oct. 2006 à 14:06
0
Utile
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
Darksnakes 19 Messages postés samedi 21 octobre 2006Date d'inscription 14 mars 2007 Dernière intervention - 21 oct. 2006 à 14:45
0
Utile
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
Darksnakes 19 Messages postés samedi 21 octobre 2006Date d'inscription 14 mars 2007 Dernière intervention - 21 oct. 2006 à 15:20
0
Utile
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
Pole4 20 Messages postés mardi 11 octobre 2005Date d'inscription 13 mars 2007 Dernière intervention - 22 oct. 2006 à 10:15
0
Utile
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.