Algorithme (nombre premier)
Dr.Mimo
Messages postés
4
Date d'inscription
Statut
Membre
Dernière intervention
-
Heliotte Messages postés 1491 Date d'inscription Statut Membre Dernière intervention -
Heliotte Messages postés 1491 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Sarah Armiss
#include<stdio.h>
#include<conio.h>
int main()
{
int n,x,i;
printf("Entrez un nombre entier superieur a 1 (>1): ");
do{
scanf("%d",&n); }
while(n<=1);
x=0;
for(i=2;i<=(n/2);i++)
{
if(n % i == 0)
{x++;}
}
if(x>0){printf("ce nombre n'est pas premier");} else {printf("ce nombre est premier");}
getch();
}
Sarah Armiss
#include<stdio.h>
#include<conio.h>
int main()
{
int n,x,i;
printf("Entrez un nombre entier superieur a 1 (>1): ");
do{
scanf("%d",&n); }
while(n<=1);
x=0;
for(i=2;i<=(n/2);i++)
{
if(n % i == 0)
{x++;}
}
if(x>0){printf("ce nombre n'est pas premier");} else {printf("ce nombre est premier");}
getch();
}
A voir également:
- Algorithme verifier si un nombre est premier
- Algorithme qui détermine si un nombre est premier - Meilleures réponses
- Algorithme premier - Meilleures réponses
- Verifier compatibilite windows 11 - Guide
- Verifier un lien - Guide
- Vérifier si mot de passe piraté - Guide
- Cheick yvann premier jour - Forum Wii U
- Nombre de jours entre deux dates excel - Guide
4 réponses
"Mais l'algorithme marche sans problème ... normalement. (essayé)"
Oui, mais tu as demandé "le critiquer si il contient des défauts"
Ce que Heliotte veut dire (je pense) c'est qu'il n'est pas utile de faire ton x++ et donc compter le nombre de diviseurs, car il suffit qu'il y en ait un seul pour que ce ne soit pas un nombre premier. Si par exemple ton nombre est pair, tu dois t'arrêter dès que tu as vu que c'était divisible par 2, pas continuer comme tu le fais jusqu'à n/2.
De plus le choix de n/2 est également mauvais, en effet le plus grand diviseur d'un nombre sera sqrt(n), on aura alors n=sqrt(n)*sqrt(n), c'est inutile de chercher des diviseurs au delà. Dans le détail, si n est divisé par d>sqrt(n) cela signifie qu'il est aussi divisé par n/d<sqrt(n), c'est à dire qu'on aura déjà identifié le diviseur !
Remarque : il est également inutile de tester des diviseurs pairs (à part 2), car si le nombre est divisible par un nombre pair, alors 2 l'aura déjà divisé. Donc au lieu de tester tout les i, tu peux te limiter aux impairs :
Oui, mais tu as demandé "le critiquer si il contient des défauts"
Ce que Heliotte veut dire (je pense) c'est qu'il n'est pas utile de faire ton x++ et donc compter le nombre de diviseurs, car il suffit qu'il y en ait un seul pour que ce ne soit pas un nombre premier. Si par exemple ton nombre est pair, tu dois t'arrêter dès que tu as vu que c'était divisible par 2, pas continuer comme tu le fais jusqu'à n/2.
De plus le choix de n/2 est également mauvais, en effet le plus grand diviseur d'un nombre sera sqrt(n), on aura alors n=sqrt(n)*sqrt(n), c'est inutile de chercher des diviseurs au delà. Dans le détail, si n est divisé par d>sqrt(n) cela signifie qu'il est aussi divisé par n/d<sqrt(n), c'est à dire qu'on aura déjà identifié le diviseur !
Remarque : il est également inutile de tester des diviseurs pairs (à part 2), car si le nombre est divisible par un nombre pair, alors 2 l'aura déjà divisé. Donc au lieu de tester tout les i, tu peux te limiter aux impairs :
int x=1;
if (n%2==0)
x=(n==2);
else
{
int s = (int) sqrt(n);
for (i=3; i<=s; i+=2)
if(n % i == 0)
{
x=0;
break;
}
}
if (x)
printf("ce nombre est premier");
else
printf("ce nombre n'est pas premier");
Je voulais faire simple, mais cette proposition est très complète .. milles mercis.