Langace C, Nombre parfait

Fermé

keurdange

Messages postés: 718
Date d'inscription: lundi 8 novembre 2010
Statut: Membre
Dernière intervention: 13 juillet 2016

- 9 avril 2011 à 19:24
KX

Messages postés: 16520
Date d'inscription: samedi 31 mai 2008
Statut: Modérateur
Dernière intervention: 16 mai 2022

- 9 août 2011 à 14:18

Bonjour,

je suis debutant en langage et j'aimerais faire un programme qui teste si un nombre un parfait (on dit qu'un nombre est parfait s'il est égal à à la somme de ses diviseurs sauf lui même. exemple 6. Preuve: 6=3+2+1 et 6/1=6,6/2=3,6/3=2).
voici mon programmme

#include<stdio.h>
int nbr,n,som,quotient;
main()
{
do
{
printf("Entrez le nombre à tester: ");
scanf("%d", &nbr);
}
while(nbr<0);
som=0;
for(n=1;n=nbr-1;n++)
{
if(nbr%n==0)
{
quotient=nbr/n;
if(quotient==n)
som=som+1;
if(quotient!=n)
som=som+2;
}
}
if(som==nbr)
printf("%d est un nombre parfait", nbr);
else
printf("%d n'est pas un nombre parfait", nbr);
}

mais à l'exécution (je suis sous ubuntu), le curseur revient à la ligne et puis rien ne se passe.
aidez moi.

Merci

A voir également:

Nombre parfait en c
Algorithme nombre parfait en c - Meilleures réponses
Nombre parfait langage c - Meilleures réponses
Nombre parfait python - Forum - Programmation
Langace C, Nombre parfait - Forum - Programmation
Nombre parfait algorithme - Forum - Pascal
Nombre parfait ✓ - Forum - C
Nombre parfait java - Forum - Java

3 réponses

Réponse 1 / 3

Messages postés: 16520
Date d'inscription: samedi 31 mai 2008
Statut: Modérateur
Dernière intervention: 16 mai 2022

2 962
Modifié par KX le 20/06/2011 à 08:23

Comme le disait Arya Dröttningu, ton erreur est dans la boucle for, en effet n=nbr-1 n'est pas une condition d'arrêt, c'est une affection, et du coup ta boucle ne s'arrête jamais... Modifies ça en n<=nbr-1 ou n<nbr et ça se terminera.

Remarque : ton calcul est faux, je l'ai testé entre 1 et 10000, il trouve 2 (qui n'est pas parfait) et 6 alors qu'on devrait trouver 6, 28, 496 et 8128...

Réponse 3 / 3

genesis
19 juin 2011 à 22:17

premièrement sache qu'un diviseur ne dépasse jamais la racine carre du nombre. Bon, j'ai écrit le programme, à toi de voir, je néglige les premières étapes. Je signale juste que j'ai inclue la bibliothèque <math.h> pour pouvoir utilisé la fonction sqrt qui détermine la racine carrée.

int i, som = 0;

for (i = 1 ; i <= sqrt (N); i ++)
{
if (N%i == 0)
{som += i;}
}

if (som == N)
{printf ("%d est parfait", N); }

else {printf ("%d n'est pas parfait", N); }

Messages postés: 16520
Date d'inscription: samedi 31 mai 2008
Statut: Modérateur
Dernière intervention: 16 mai 2022

2 962
Modifié par KX le 20/06/2011 à 06:20

Petite remarque théorique ^^
"un diviseur ne dépasse jamais la racine carre du nombre"... non pas tout à fait !

La seule chose qu'on peut dire c'est que si un nombre n'a pas de diviseur inférieur à sa racine carrée il est premier.

Par exemple 28 = 1 + 2 + 4 + 7 + 14 est un nombre parfait, et pourtant 7 et 14 sont des diviseurs supérieurs à sa racine carrée (environ 5,3)

Donc dans la boucle c'est jusqu'à i<=N/2 qu'il faut aller si on fait som+=i
Ou alors il faudrait rajouter som+=i+N/i mais faire très attention au cas de i=1 (pour ne pas rajouter N) et à l'égalité i==sqrt(N) pour ne pas compter deux fois sqrt(N)

genesis
Modifié par genesis le 19/06/2011 à 23:42

Ah oui, ça ne dépasse pas la moitié dsl, je me suis trompé ^^ donc jusqu'à N/2. Comme ça, y a pas besoin de soustraire le N vers la fin ou d'enlever un cas d'égalité.

Messages postés: 16520
Date d'inscription: samedi 31 mai 2008
Statut: Modérateur
Dernière intervention: 16 mai 2022

2 962
Modifié par KX le 20/06/2011 à 07:37

Mais du coup si on coupe à N/2 on perd en performance...
Pour atteindre de grands nombres, il est bien plus intéressant de couper le calcul à la racine carrée même si ça nécessite de faire un petit peu plus de calcul(et de code) à chaque itération.

Exemple : 137 438 691 328 est le 7è nombre parfait
Si on coupe à N/2 il va donc falloir faire près de 69 milliards d'itérations --'
Si on coupe à racine de N il ne faudra "que" 371 millions d'itérations, ce que mon ordinateur peut faire en moins d'une seconde avec l'implémentation ci-dessous :

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  

int nombreParfait(const unsigned long long n)  
{  
    unsigned long long   
        racine = sqrt((double) n),  
        somme = 1;  
      
    if (racine*racine==n)  
    {  
        somme+=racine;  
        racine--;  
    }  
      
    for (unsigned long long i=2; i<=racine; i++)  
    {  
        if (n%i==0)  
        {  
            somme+= i;  
            somme+= n/i;  
        }  

        if (somme>n)  
            return 0;  
    }  
      
    return somme==n;  
}  

void afficherNombreParfait(const unsigned long long n)  
{  
    if (nombreParfait(n))  
        printf("%llu est un nombre parfait\n",n);  
    else  
        printf("%llu n'est pas un nombre parfait\n",n);  
}  

int main()  
{  
    for (unsigned i=1; i<30; i++)  
        afficherNombreParfait(i);  
    printf("\n");  

    afficherNombreParfait(137438691328);  
    printf("\n");  

    system("PAUSE");  
    return 0;  
}

Mais cet algo reste assez naïf, on peut faire mieux en travaillant sur les propriétés des nombres parfaits (cf. Nombre parfait sur Wikipédia)

memeli .tm
9 août 2011 à 14:06

pour mieux simplifié la boucle for ,il faudra changer la condition placée au lieu de :
for(i=1;i <= sqrt (N);i++) utilisé : for(i=1;i<=(N)/2;i++) car un diviseur d'un nombre ne depasse jamais la moiité de celui-ci. dans cas le programme se presentera comme suite:

#include<stdio.h>
#include<stdlib.h>
int main()
{

int N,i,som,;

printf("Entrez le nombre à tester: ");

scanf("%d", &nbr);

for(i=1;i<=(N)/2;i++)
{
if (N%i == 0)

som=0;

{som += i} ;
}

if (som == N)
}
{printf ("%d est parfait", N); }

else {printf ("%d n'est pas parfait", N); }
}
}
system("PAUSE");
return 0;
}

Messages postés: 16520
Date d'inscription: samedi 31 mai 2008
Statut: Modérateur
Dernière intervention: 16 mai 2022

2 962
9 août 2011 à 14:18

Simplifier la boucle, c'est utile pour le programmeur, ça lui évite de se casser la tête, mais c'est mauvais en performance car faire un algo en O(N) ou en O(racine(N)) c'est quand même très différent !
Je l'ai d'ailleurs expliqué juste au dessus avec l'exemple du 7è nombre parfait...

Discussions similaires

Calcul de la somme des chiffres d'un nombre

Tri alphabétique

Algo affichage combinaison de p elemt parmi n

langage c: calcul longueur d une chaine

Exercice simple d'algorithmique

algorithme qui calcule somme < >!!

Discussions similaires

Newsletters