Algorithme (nombre premier) [Fermé]

Signaler
Messages postés
4
Date d'inscription
samedi 1 décembre 2012
Statut
Membre
Dernière intervention
1 décembre 2012
-
Messages postés
1491
Date d'inscription
vendredi 26 octobre 2012
Statut
Membre
Dernière intervention
28 janvier 2013
-
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();
}

4 réponses

Messages postés
16258
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
28 février 2021
2 800
"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 :

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");
2
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci

Messages postés
1491
Date d'inscription
vendredi 26 octobre 2012
Statut
Membre
Dernière intervention
28 janvier 2013
85
Excellent KX !
Je voulais faire simple, mais cette proposition est très complète .. milles mercis.
Messages postés
4
Date d'inscription
samedi 1 décembre 2012
Statut
Membre
Dernière intervention
1 décembre 2012

Je souhaite que tout le monde vont bénéficier de cet algorithme et le critiquer si il contient des défauts, Merci.
Messages postés
1491
Date d'inscription
vendredi 26 octobre 2012
Statut
Membre
Dernière intervention
28 janvier 2013
85
Définition : un nombre premier n'est divisible que par 1 et par lui-même.
Partant de ce principe, si un nombre est divisible par un autre nombre que "1" et ce même nombre alors ce n'est pas un nombre premier.
Donc:
SI (Nombre MOD UnAutreNombre == 0) ALORS "Ce n'est pas un nombre premier !"
Messages postés
4
Date d'inscription
samedi 1 décembre 2012
Statut
Membre
Dernière intervention
1 décembre 2012

Mais l'algorithme marche sans problème ... normalement. (essayé)