Nombres premiers en language c [Fermé]

Signaler
-
 Andrea -
Déjà bonjours à tous,
Mon problème est de trouver des nombres premiers. En fait sur des entiers de 0 à 100, je dois faire un programme (en language c)qui compte le nombre de nombres premiers et qui ensuite les affiches. Mais moi je ne sais pas du tout comment trouver ces nombres, comment les calculer. On m'a vaguement parler des modulos etc. mais je n'ai jamais appris réellement à m'en servir alors si quelqu'un pouvais m'aider...
merci d'avance.

18 réponses

salut le modulos c le rest de la division d'un nombre sure un autre nombre
et pour les chiffres premiers il faux que le modulos du chiffre=0 avec deux nombres seulement donc il est divisable sur lui meme et sur 1 et voici le code en c qui définis les nombrs premiers qui sont inférieur du nombres saisis
*******************************
#include<stdio.h>
void main ()
{
int nbr;
int m=0;
printf("Veuillez entrer un nombre entier:");
scanf("%i",&nbr);
printf("Les nombres premiers sont:\n");
while(nbr>=2){
for(int i=1;i<=nbr;i++){
if(nbr%i==0){m++;}
}
if(m==2){
printf("%i\n",nbr,"Ce nombre est premier.");
}
m=0;
nbr--;
}
}
*****************************
si tu trouve le programme de simplexe stp tu me l'nvois sur mon e-mail j'en ai vraiment besoin
merci nounou-03@live.com
16
Merci

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

CCM 59928 internautes nous ont dit merci ce mois-ci

Construire l’algorithme de recherche des nombres parfaits compris entre 1 et 1000 en sachant qu’un nombre parfait est égale à la somme de ses diviseurs excepté lui-même.
Debut
Pour N allant de 1 à 1000 faire
DPour
Som 0
Pour i allant de 1 à N div 2 faire
DPour
C N mod i
Si C = 0 alors Som Som+i
FPour
Si N = Som alors ecrire ( N )
FPour
FIN
#include<stdio.h>

int main()
{


int LeNb, Div, Cpt;

printf("Entrez votre Nombre pour savoir si il est premier ou non\n");
scanf("%d", &LeNb);

Div = LeNb - 1;

if (((LeNb % 2) == 0) && (LeNb != 2)) {
printf("Nombre non premier\n");
}

else {

while (((LeNb % Div) != 0) && (Div >= 1)){
Div--;}


if ((Div == 1) && (LeNb / LeNb == 1)){
printf("Nombre premier\n");
}
else {
printf("Nombre non premier\n");}
}
}
Messages postés
144
Date d'inscription
jeudi 14 septembre 2006
Statut
Membre
Dernière intervention
6 juin 2010
33
SLT A TOUS
je sais qu'il est tard pour une réponse mais je laisse mon programme au passage.
J'espère que cela aidera certaine personne.
ce prog te donne le nombre de diviseur d'un nombre.

#include <stdio.h> 

main () 
{ 
     int nbre, rest, test, i; 
     printf("Entrer un nombre: "); 
     scanf("%d", &nbre); 
     test = 0; 
      
     for(i = 1; i <= nbre; i++) 
     { 
        rest = nbre%i;  

        if(rest == 0)  
        {  
           test += 1;  
           } 
     } 
     printf("\nCe nombre '%d' saisi a %d Diviseur\n", nbre, test); 
     if(test == 2)  
     { 
        printf("\nCe nombre est donc premier"); 
        } 
     else  
     { 
         printf("\nLe nombre '%d' saisi n'est pas premier", nbre); 
         } 
      
     getch(); 
     } 


Cordialement !!
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630
Remarques :

Tu peux commencer ta boucle for à 2, et l'arrêter à sqrt(nbre), en effet au delà de la racine carré, il n'existe aucun nombre qui divise nbre (à part nbre lui même), ce qui diminue le nombre de calcul à faire (exemple pour 1000000, tu ne fera "que" 9999 calculs)
Dans ce cas, tu auras test+2 diviseurs et donc tu feras if (test+2==2) ou if (test==0) ou if (!test)

Le nom des variables est mal choisi, surtout test, il aurait mieux fallu la nommer nbreDiv par exemple pour nombre de diviseurs...

Tu n'as pas besoin de la variable Quest, tu peux directement faire, if (nbre%i ==0)

test++; est bien plus joli que test+=1; ... oui, je chipote ;-)

Le \n sert à passer à la ligne, il est plus judicieux de le mettre à la fin d'une ligne, et non pas au début, d'autant que parfois la ligne ne s'affiche pas s'il n'y a pas eu de \n après.

Mes remarques ne sont pas exhaustives, mais elles t'aideront à améliorer ton code et à prendre de bonnes habitudes... Bon courage pour la suite !
Messages postés
144
Date d'inscription
jeudi 14 septembre 2006
Statut
Membre
Dernière intervention
6 juin 2010
33
slt ,
merci pour les commentaires,
pourrais tu m'envoyer un programme plus net ?
aussi peux tu m'aider à demander si l'utilisateur veut calculer un autre nombre

et celui-ci (après correction)

#include <stdio.h>

main ()
{
int nbre, nbreDiv, i;
printf("Entrer un nombre: ");
scanf("%d", &nbre);
nbreDiv = 0;

for(i = 2; i <= sqrt(nbre); i++)
{

if(nbre%i == 0)
{
nbreDiv++;
}
}

if(!nbreDiv)
{
printf("Ce nombre est donc premier");
}
else
{
printf("Le nombre '%d' saisi n'est pas premier", nbre);
}

getch();
}
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630
Je n'ai pas modifié l'algorithme que tu as proposé (avec correction), parce que c'est le meilleur pour ce que tu veux faire.

Par contre je l'ai découpé en plusieurs fonctions ce qui gagne en netteté.
Et bien sûr, j'ai fais en sorte qu'il marche, avec un affichage simple et clair, en gérant les cas particuliers les plus fréquents.

Remarque : pour insérer du code, utilise les balise < code> et < /code>, soit manuellement, soit en utilisant le bouton fait exprès (à droite du bouton souligné)

#include <stdio.h> // printf, scanf
#include <math.h>  // sqrt
    
    
short demanderContinuer(void)
{
    printf("Voulez vous continuer ? (y/n) ");
    char s[10];
    scanf("%s",s);
    
    switch (s[0]) // on regarde le premier caractère
    {
        case 'n' : return 0; // on s'arrête
        case 'y' : return 1; // on continue
        default  : return demanderContinuer(); // on redemande
    }
}


long demanderNombre(void)
{
    long nbre;
    printf("Entrez un nombre >1 : "); 
    scanf("%ld", &nbre); 
    
    if (nbre>1)
    {
        return nbre;
    }
    else
    {
        return demanderNombre(); // on redemande
    }
}


long nombreDiviseur(long nbre)
{
    printf("\n1\n");
    
    if (nbre==2) // cas particulier à cause de la racine carrée
    {            // sinon, on compterait deux fois le 2 !!!
        printf("2\n");
        return 2;
    }
    
    long i, nbreDiv=2; // deux diviseurs : 1 et nbre
    
    for (i=2; i<=sqrt(nbre); i++) 
    { 
        if(nbre%i == 0)
        {
            nbreDiv++; // un diviseur de plus : i
            printf("%ld\n",i); // on l'affiche
        }
    } 
    printf("%ld\n",nbre);
    return nbreDiv;
}


void uneRecherche(void)
{        
    long nbre=demanderNombre();
    long nbreDiv=nombreDiviseur(nbre);
    
    printf("\n%d a %d diviseurs ",nbre,nbreDiv);    
    if (nbreDiv>2)
    {
        printf("il n'est donc pas premier\n\n");
    }
    else
    {
        printf("il est donc premier\n\n");
    }          
}


int main(void) 
{ 
    do
    {
         printf("\n");
         uneRecherche();
    }
    while(demanderContinuer());
    
    return 0;
}
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630
Je tiens à rectifier une grosse erreur de maths !
Un nombre donné, peut avoir des diviseurs supérieurs à sa racine carré.
Exemple : sqrt(8)=2,8 mais 4 qui est plus grand est bien un diviseur de 8

Toutefois on peux trouver ces diviseurs sans itérer au delà de la racine carrée.
Cela modifie donc un peu le code...

long nombreDiviseur(long nbre)
{
    long i, nbreDiv=0;
    float racine=sqrt(nbre);

    for (i=1; i<=racine; i++)
    {
        if(nbre%i == 0)
        {
            if (i==racine)
	    {
	 	nbreDiv++; // un diviseur de plus : racine
		printf("%ld\n",i); // on l'affiche
	    }
	    else
	    {
		nbreDiv+=2; // deux diviseurs de plus : i et nbre/i
		printf("%ld\n%ld\n",i,nbre/i); // on les affiche
	    }
        }
    }

    return nbreDiv;
}
Messages postés
1621
Date d'inscription
vendredi 26 novembre 2004
Statut
Membre
Dernière intervention
30 mars 2006
144
si ton échantillon est petit tu peux utilser un crible
tu définis une array de boolean de 2 à cardinal de l'ensemble valeur true
testé par exemple 1000 000
ensuite tu demarres à 2
et tu fais une boucle step 2 à 1000000 tous les nombres trouvés
sont mutilpes de 2 et tu les mets à faux
tu recherches le premier premier dans ton array ce sera 3 puis 5
toujours une boucle 3 et 5 qui met à faux leurs mutilples
l'algo s'arrete quand tu arrives à la racine du nombre
c'est le crible d'eratosthène (?)
par contre pour les grands nombres c'est lèger comme solution
Messages postés
23761
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
13 janvier 2020
2 855
Voui, si on s'arrête à 100, mais au-delà, non !

143 = 13 x 11, par exemple, n'est divisible ni par 2, 3, 5 ou 7...

J'ai parlé du cas général...

A+ Blux
 "Les cons, ça ose tout.
C'est même à ça qu'on les reconnait"
Messages postés
29
Date d'inscription
mardi 11 janvier 2005
Statut
Membre
Dernière intervention
18 février 2005
14
Comme je l'ai écrit, je pense que 2,3,5 et 7 suffisent, innutil de tenter de diviser par tous les nombres premiers déjà trouver :)

----
L'orthographe est primordiale sur un forum,
la politesse l'est encore plus.
Messages postés
29
Date d'inscription
mardi 11 janvier 2005
Statut
Membre
Dernière intervention
18 février 2005
14
Dans ce cas oui tu as raison, c'est utile de le préciser. ;)

----
L'orthographe est primordiale sur un forum,
la politesse l'est encore plus.

tu me donner le programme en caml light svp j'ai besoin la solution
merci
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630
let EstPremier n =
    let b=ref true in
    for i=2 to n-1 do
        b := !b && (n mod i>0)
    done;
    n>1 && !b;;
En effet, 1 contredit la définition des nombres premiers qui est
"Un nombre est premier ssi il admet exactement deux diviseurs distincts, 1 et lui-même"
Donc 1 n'est pas premier

PS: je sais que je réouvre un vieux topic mais c'est pour clore la discussion à ce sujet
Messages postés
151
Date d'inscription
dimanche 22 mars 2009
Statut
Membre
Dernière intervention
22 mars 2011
13
JE vais parler de la part du théorie : le 1 N'EST PAS UN NOMBRE PREMIER
LE 2 EST PREMIER
Mettez ca en tete .
Messages postés
23761
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
13 janvier 2020
2 855
et alors, c'est une raison pour être aussi agressif ?
Messages postés
151
Date d'inscription
dimanche 22 mars 2009
Statut
Membre
Dernière intervention
22 mars 2011
13 >
Messages postés
23761
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
13 janvier 2020

non pas ca mais j'ai constaté cette grave erreure qui ne doit pas psser inapercue
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630 >
Messages postés
23761
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
13 janvier 2020

Mais cette erreur avait déjà été corrigée à plusieurs reprises...
Inutile de retourner indéfiniment le couteau dans la plaie (surtout sur un vieux post)
Messages postés
151
Date d'inscription
dimanche 22 mars 2009
Statut
Membre
Dernière intervention
22 mars 2011
13
Ok Ok
merci...
je crois que j'ai pigé le truc alors je vais essayer. a+
salut,
voilà tous simplement un nombre premier accepte la division par 1 et pa lui même donc le nbre de diviseurs est 2
voici en pascal
cptenp:=0;
for i:=1 to 100 do
begin
s:=0;
for j:=1 to i do
begin
if i mod j =0 then
s:=s+1;
end;{boucle de j}
if s=2 then
begin
cptenp:=cptenp+1;
A[cptenp]:=i
end;{fin de la boucle i}
writeln ("le nombre des nombres premiers",cptenp);
for i:=1 to cptenp do
writeln ("A[",i,"]",A[i]);
end.
bonne chance.
Merci
bonne chance.
Merci.
Messages postés
1621
Date d'inscription
vendredi 26 novembre 2004
Statut
Membre
Dernière intervention
30 mars 2006
144 > aldo13
1 répond à la définition
il ne connaît que deux diviseurs 1 et lui même

elle est pas belle, la vie ?
>
Messages postés
1621
Date d'inscription
vendredi 26 novembre 2004
Statut
Membre
Dernière intervention
30 mars 2006

1 ne devrait pas etre listé comme nombre premier.
> aldo13
Salut,
1 n'est effectivement pas premier car justement il ne correspond pas à la définition puisqu'il n'admet qu'un diviseur (1 et lui-même étant identique en l'occurence).

A++
Messages postés
1621
Date d'inscription
vendredi 26 novembre 2004
Statut
Membre
Dernière intervention
30 mars 2006
144 > Ravachol
1 est premier comme deux est pair


elle est pas belle, la vie ?
>
Messages postés
1621
Date d'inscription
vendredi 26 novembre 2004
Statut
Membre
Dernière intervention
30 mars 2006

un nombre premier est >1
et je suis formel..
L'algorithme le plus rapide : Le Crible d'Ératosthène

https://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne
Messages postés
29
Date d'inscription
mardi 11 janvier 2005
Statut
Membre
Dernière intervention
18 février 2005
14
Je ne voudrais pas dire de bétise, j'avais fait ce programme en Turbo Pascal il y a un petit moment, en gros l'algo c'est ça je crois :

Pour i de 1 à 100
Diviser i par 2
Diviser i par 3
Diviser i par 5
Diviser i par 7
Si un seul des restes de ces divisions est égal à 0 le nombre n'est pas premier.
Aprés c'est logique si aucun est égal a 0 ben tu l'affiches car il est premier ;)
J'espère que ça pourras t'aider.
Après je connais pas ton niveau en c++, si tu as des problème avec la syntaxe demande, peut être que quelqu'un pourra t'aider plus que moi.

----
L'orthographe est primordiale sur un forum,
la politesse l'est encore plus.
Messages postés
23761
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
13 janvier 2020
2 855
Salut,

les nombres premiers sont ceux qui ne sont divisibles que par eux-mêmes et par 1.

Il faut donc exclure tous ceux qui sont pairs (divisibles par deux), divisibles par 3 (somme des chiffres divisible par 3), qui se terminent par 5 (multiples de 5) ainsi que tous les nombre que l'on a pu tester jusqu'à présent et qui se sont révélés premiers (7, 11, 13...)

Pour savoir si un nombre est divisible par un autre, il faut appliquer la fonction 'modulo' qui renvoie le reste de la division.

Exemple :

10 modulo 3 = 1, le reste est non nul, donc le nombre n'est pas divisible.

12 modulo 4 = 0, le reste est nul, 12 est donc divisible par 3.

Cette fonction s'appelle aussi 'division euclidienne' ou 'division entière'...

Tu trouveras facilement avec google des exemples de programmes calculant les nombres premiers, ainsi que des méthodes pour accélérer les traitement (cette recherche est la base de nombreux systèmes de cryptographie...)

A+ Blux
 "Les cons, ça ose tout.
C'est même à ça qu'on les reconnait"
Messages postés
23761
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
13 janvier 2020
2 855
12 modulo 4 = 0, le reste est nul, 12 est donc divisible par 3.

Divisible par 4, bien sûr et non par 3... ;-)
Enfin, il est divisible par 3, mais c'est pas avec 'modulo' qu'on le sait...

A+ Blux
 "Les cons, ça ose tout.
C'est même à ça qu'on les reconnait"
Messages postés
144
Date d'inscription
jeudi 14 septembre 2006
Statut
Membre
Dernière intervention
6 juin 2010
33
Merci le frère, ça marche nickel

Merci de ton aide.

Je viens de t'en voyer un message perso
voici un petit programme que j'ai codé en langage c pour repondre à votre question :
#include<stdio.h>
#include<conio.h>
main()
{
      int i,p;
    p=1;
    printf("( ");
    for(i=2;i<100;i++)
 {
      
        if((i==2)||((i%2!=0)&&(i%3!=0)&&(i%5!=0)&&(i%7!=0)))
        {
            p=p+1      ;                              
                  printf("%i ",i);
                  }
                  }
                  printf(")");
                  printf("\nle nombre des entiers premier compris entre 0 et 100 est : %i",p);
        getch();
        return 0;
        }         
      
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630
Désolé d'avoir à te le dire Amine, mais ton programme est pas terrible !
En effet le résultat que tu obtiens n'est pas correct (il manque le 3, le 5 et le 7)
De plus un bon algorithme doit pouvoir être utilisé aussi largement que possible (c'est à dire qu'il doit resté vrai si on considère un intervalle plus grand) or ici à peine arrivé à 121 (multiple de 11) on se retrouve avec des nombres premiers qui n'en sont en fait pas !
bonjour eu tout nombre entier qui se termine par 5 a un carré qui se termine par 25 mais comment on peut en etre sur svp
Messages postés
15933
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 juillet 2020
2 630
Avec une identité remarquable tout simplement...