Comment afficher les nombres premiers en C
Un nombre premier est tout nombre qui admet deux diviseurs entiers et positifs qui sont le 1 et le nombre lui-même. 1 n'est pas considéré comme nombre premier parce qu'il admet qu'un diviseur. Le 0 aussi puisqu'il est divisible par tous les nombres.
Deux façon pour vérifier si p est un nombre premier :
- Le reste de la division est nul pour tous les nombres inférieurs sauf le 1 et le nombre p .
- La théorème de Wilson énonce qu'un entier est premier si et seulement si la factorielle de p-1 est équivalente à -1 modulo p.
(p - 1)! + 1 ≡ 0 (mod p).
Source : http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Wilson
Nous allons utiliser la première méthode.
Programme qui vérifie si un nombre entier est un nombre premier:
using namespace std; #include<iostream> #include<stdlib.h> int main() { int nb,r=0; cout<<"Entrez un nombre : ";cin>>nb; for(int i = 1 ; i <= nb ; i++ ) { if(nb % i == 0) { r++; } } if(r>2) cout<<nb<<" n'est pas un nombre premier"<<endl; else cout<<nb<<" est un nombre premier"<<endl; system("pause"); } |
Programme qui vérifie si les n nombres saisies sont des nombres premiers:
| #include<stdio.h> #include<stdlib.h> int main() { int nombre=1, compteur=0; int i,r,n=100; while(compteur<n){//les n premiers r=0;//pour compter le nombre de diviseurs nombre++; for (i=1 ; i<=nombre ; i++) { if ((nombre%i)==0) r++; } if(r==2)//Le nombre premier se divise sur 1 et sur lui meme { printf(" %d \n",nombre); //on incrémente le compteur compteur++; } } system("pause"); } |
Programme qui affiche tous les nombres premiers inférieurs à n:
| #include<stdio.h> #include<stdlib.h> int main() { int nombre=1, compteur=0; int i,r,n=100; printf("Les nombres premiers inférieurs à %d sont:\n",n); while(nombre <n){//tant que nombre < n alors r=0;//pour compter le nombre de diviseurs nombre++; for (i=1 ; i<=nombre ; i++) { if ((nombre%i)==0) r++; } if(r==2)//Le nombre premier se divise sur 1 et sur lui meme { printf(" %d \n",nombre); } } system("pause"); } |
Déroulement :
Les nombres premiers inférieurs à 100 sont :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,79, 83, 89, 97.