Que sont les nombres premiers ?
UN nombre premier est défini comme un nombre naturel supérieur à 1 et est divisible par seulement 1 et lui-même.
En d’autres termes, le nombre premier est un entier positif supérieur à 1 qui a exactement deux facteurs, 1 et le nombre lui-même. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23 . . .
Note: 1 n’est ni premier ni composite. Les nombres restants, à l'exception de 1, sont classés comme nombres premiers et composés.

nombres premiers
Quelques faits intéressants sur les nombres premiers :
- Sauf 2, qui est le plus petit nombre premier et le seul nombre premier pair, tous les nombres premiers sont des nombres impairs.
- Tout nombre premier peut être représenté sous la forme 6n + 1 ou 6n – 1 sauf les nombres premiers 2 et 3 , où n est n'importe quel nombre naturel.
- 2 et 3 ne sont que deux nombres naturels consécutifs premiers.
- Conjecture de Goldbach : Tout entier pair supérieur à 2 peut être exprimé comme la somme de deux nombres premiers.
- Théorème de Wilson : Le théorème de Wilson stipule qu’un nombre naturel p> 1 est un nombre premier si et seulement si
(p-1) ! ≡ -1 contre p
OU,
(p-1) ! ≡ (p-1)mod p
- Le petit théorème de Fermat : Si n est un nombre premier, alors pour tout a, 1 ≤ a
unn-1≡ 1 (mod n)
OU,
unn-1% n = 1
- Théorème des nombres premiers : La probabilité qu'un nombre n donné choisi au hasard soit premier est inversement proportionnelle à son nombre de chiffres, ou au logarithme de n.
- La conjecture de Lemoine : Tout entier impair supérieur à 5 peut être exprimé comme la somme d'un nombre premier impair (tous les nombres premiers autres que 2 sont impairs) et d'un nombre premier pair. Un nombre semi-premier est le produit de deux nombres premiers. C’est ce qu’on appelle la conjecture de Lemoine.
Propriétés des nombres premiers :
- Tout nombre supérieur à 1 peut être divisé par au moins un nombre premier.
- Tout entier pair positif supérieur à 2 peut être exprimé comme la somme de deux nombres premiers.
- Sauf 2, tous les autres nombres premiers sont impairs. En d’autres termes, on peut dire que 2 est le seul nombre premier pair.
- Deux nombres premiers sont toujours premiers entre eux.
- Chaque nombre composé peut être pris en compte en facteurs premiers et, individuellement, tous sont de nature unique.
Nombres premiers et nombres co-premiers :
Il est important de faire la distinction entre nombres premiers et nombres premiers entre eux . Vous trouverez ci-dessous les différences entre les nombres premiers et co-premiers.
- Les nombres premiers sont toujours considérés comme une paire, alors qu'un nombre premier est un nombre unique.
- Les nombres co-premiers sont des nombres qui n'ont pas de facteur commun sauf 1. En revanche, les nombres premiers n'ont pas une telle condition.
- Un nombre copremier peut être premier ou composé, mais son plus grand facteur commun (GCF) doit toujours être 1. Contrairement aux nombres composés, les nombres premiers n'ont que deux facteurs, 1 et le nombre lui-même.
- Exemple de co-prime : 13 et 15 sont co-primes. Les facteurs de 13 sont 1 et 13 et les facteurs de 15 sont 1, 3 et 5. Nous pouvons voir qu'ils n'ont que 1 comme facteur commun, ce sont donc des nombres premiers entre eux.
- Exemple de premier : Quelques exemples de nombres premiers sont 2, 3, 5, 7 et 11, etc.
Comment vérifier si un numéro est Prime ou non ?
Approche naïve : L'approche naïve consiste à
Itérer de 2 à (n-1) et vérifier si un nombre dans cette plage divise n . Si le nombre divise n , alors ce n'est pas un nombre premier.
Complexité temporelle : SUR)
Espace auxiliaire : O(1)
Approche naïve (récursive) : La récursivité peut également être utilisée pour vérifier si un nombre compris entre 2 à n – 1 divise n. Si nous trouvons un nombre qui divise, nous renvoyons faux.
Vous trouverez ci-dessous la mise en œuvre de l’idée ci-dessus :
C++
// C++ program to check whether a number> // is prime or not using recursion> #include> using> namespace> std;> > // function check whether a number> // is prime or not> bool> isPrime(> int> n)> {> > static> int> i = 2;> > > // corner cases> > if> (n == 0 || n == 1) {> > return> false> ;> > }> > > // Checking Prime> > if> (n == i)> > return> true> ;> > > // base cases> > if> (n % i == 0) {> > return> false> ;> > }> > i++;> > return> isPrime(n);> }> > // Driver Code> int> main()> {> > > isPrime(35) ? cout <<> ' true
'> : cout <<> ' false
'> ;> > return> 0;> }> > // This code is contributed by yashbeersingh42> |
>
>
Java
// Java program to check whether a number> // is prime or not using recursion> import> java.io.*;> > class> GFG {> > > static> int> i => 2> ;> > > // Function check whether a number> > // is prime or not> > public> static> boolean> isPrime(> int> n)> > {> > > // Corner cases> > if> (n ==> 0> || n ==> 1> ) {> > return> false> ;> > }> > > // Checking Prime> > if> (n == i)> > return> true> ;> > > // Base cases> > if> (n % i ==> 0> ) {> > return> false> ;> > }> > i++;> > return> isPrime(n);> > }> > > // Driver Code> > public> static> void> main(String[] args)> > {> > if> (isPrime(> 35> )) {> > System.out.println(> 'true'> );> > }> > else> {> > System.out.println(> 'false'> );> > }> > }> }> > // This code is contributed by divyeshrabadiya07> |
>
>
Python3
# Python3 program to check whether a number> # is prime or not using recursion> > # Function check whether a number> # is prime or not> > > def> isPrime(n, i):> > > # Corner cases> > if> (n> => => 0> or> n> => => 1> ):> > return> False> > > # Checking Prime> > if> (n> => => i):> > return> True> > > # Base cases> > if> (n> %> i> => => 0> ):> > return> False> > > i> +> => 1> > > return> isPrime(n, i)> > > # Driver Code> if> (isPrime(> 35> ,> 2> )):> > print> (> 'true'> )> else> :> > print> (> 'false'> )> > # This code is contributed by bunnyram19> |
>
>
C#
// C# program to check whether a number> // is prime or not using recursion> using> System;> class> GFG {> > > static> int> i = 2;> > > // function check whether a number> > // is prime or not> > static> bool> isPrime(> int> n)> > {> > > // corner cases> > if> (n == 0 || n == 1) {> > return> false> ;> > }> > > // Checking Prime> > if> (n == i)> > return> true> ;> > > // base cases> > if> (n % i == 0) {> > return> false> ;> > }> > i++;> > return> isPrime(n);> > }> > > static> void> Main()> > {> > if> (isPrime(35)) {> > Console.WriteLine(> 'true'> );> > }> > else> {> > Console.WriteLine(> 'false'> );> > }> > }> }> > // This code is contributed by divyesh072019> |
>
>
Javascript
> > // JavaScript program to check whether a number> > // is prime or not using recursion> > > // function check whether a number> > // is prime or not> > var> i = 2;> > > function> isPrime(n) {> > > // corner cases> > if> (n == 0 || n == 1) {> > return> false> ;> > }> > > // Checking Prime> > if> (n == i)> return> true> ;> > > // base cases> > if> (n % i == 0) {> > return> false> ;> > }> > i++;> > return> isPrime(n);> > }> > > // Driver Code> > > isPrime(35) ? document.write(> ' true
'> ) : document.write(> ' false
'> );> > > // This code is contributed by rdtank.> > > |
chaîne dans un tableau en c
>
>Sortir
false>
Complexité temporelle : SUR)
Espace auxiliaire : O(N) si l'on considère la pile de récursivité. Sinon, c'est O(1).
Approche efficace : Une solution efficace consiste à :
Parcourez tous les nombres de 2 à la racine carrée de n et pour chaque nombre, vérifiez s'il divise n [car si un nombre est exprimé comme n = xy et l'un des x ou y est supérieur à la racine de n, l'autre doit être inférieur à la valeur racine]. Si nous trouvons un nombre qui divise, nous renvoyons faux.
Ci-dessous la mise en œuvre :
C++14
// A school method based C++ program to> // check if a number is prime> #include> using> namespace> std;> > // Function check whether a number> // is prime or not> bool> isPrime(> int> n)> {> > // Corner case> > if> (n <= 1)> > return> false> ;> > > // Check from 2 to square root of n> > for> (> int> i = 2; i <=> sqrt> (n); i++)> > if> (n % i == 0)> > return> false> ;> > > return> true> ;> }> > // Driver Code> int> main()> {> > isPrime(11) ? cout <<> 'true
'> : cout <<> 'false
'> ;> > return> 0;> }> |
>
>
Java
// A school method based Java program to> // check if a number is prime> import> java.lang.*;> import> java.util.*;> > class> GFG {> > > // Check for number prime or not> > static> boolean> isPrime(> int> n)> > {> > > // Check if number is less than> > // equal to 1> > if> (n <=> 1> )> > return> false> ;> > > // Check if number is 2> > else> if> (n ==> 2> )> > return> true> ;> > > // Check if n is a multiple of 2> > else> if> (n %> 2> ==> 0> )> > return> false> ;> > > // If not, then just check the odds> > for> (> int> i => 3> ; i <= Math.sqrt(n); i +=> 2> ) {> > if> (n % i ==> 0> )> > return> false> ;> > }> > return> true> ;> > }> > > // Driver code> > public> static> void> main(String[] args)> > {> > if> (isPrime(> 19> ))> > System.out.println(> 'true'> );> > > else> > System.out.println(> 'false'> );> > }> }> > // This code is contributed by Ronak Bhensdadia> |
>
>
Python3
# A school method based Python3 program> # to check if a number is prime> > > # import sqrt from math module> from> math> import> sqrt> > > > # Function check whether a number> # is prime or not> def> isPrime(n):> > > # Corner case> > if> (n <> => 1> ):> > return> False> > > # Check from 2 to sqrt(n)> > for> i> in> range> (> 2> ,> int> (sqrt(n))> +> 1> ):> > if> (n> %> i> => => 0> ):> > return> False> > > return> True> > > # Driver Code> if> __name__> => => '__main__'> :> > if> isPrime(> 11> ):> > print> (> 'true'> )> > else> :> > print> (> 'false'> )> > # This code is contributed by Sachin Bisht> |
>
>
C#
// A school method based C# program to> // check if a number is prime> using> System;> > class> GFG {> > > // Function check whether a> > // number is prime or not> > static> bool> isPrime(> int> n)> > {> > // Corner case> > if> (n <= 1)> > return> false> ;> > > // Check from 2 to sqrt(n)> > for> (> int> i = 2; i <= Math.Sqrt(n); i++)> > if> (n % i == 0)> > return> false> ;> > > return> true> ;> > }> > > // Driver Code> > static> void> Main()> > {> > if> (isPrime(11))> > Console.Write(> 'true'> );> > > else> > Console.Write(> 'false'> );> > }> }> > // This code is contributed by Sam007> |
>
>
Javascript
faire pendant que java
// A school method based Javascript program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> {> > // Corner case> > if> (n <= 1)> > return> false> ;> > > // Check from 2 to n-1> > for> (let i = 2; i if (n % i == 0) return false; return true; } // Driver Code isPrime(11) ? console.log(' true') : console.log(' false'); // This code is contributed by Mayank Tyagi> |
>
>
PHP
// A school method based PHP program to // check if a number is prime // Function check whether a number // is prime or not function isPrime($n) { // Corner case if ($n <= 1) return false; // Check from 2 to n-1 for ($i = 2; $i <$n; $i++) if ($n % $i == 0) return false; return true; } // Driver Code if(isPrime(11)) echo('true'); else echo('false'); // This code is contributed by Ajit. ?>> |
>
>Sortir
true>
Complexité temporelle : O(sqrt(n))
Espace auxiliaire : O(1)
Une autre approche efficace : Pour vérifier si le nombre est premier ou non, suivez l'idée ci-dessous :
Nous traiterons de quelques nombres tels que 1, 2, 3 et des nombres divisibles par 2 et 3 dans des cas distincts et pour les nombres restants. Itérer de 5 à sqrt(n) et vérifier pour chaque itération si (cette valeur) ou (cette valeur + 2) divise n ou non et incrémenter la valeur de 6 [car tout nombre premier peut être exprimé comme 6n+1 ou 6n-1 ]. Si nous trouvons un nombre qui divise, nous renvoyons faux.
Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus :
C++
// A school method based C++ program to> // check if a number is prime> #include> using> namespace> std;> > // Function check whether a number> // is prime or not> bool> isPrime(> int> n)> > > // Driver Code> int> main()> {> > isPrime(11) ? cout <<> 'true
'> : cout <<> 'false
'> ;> > return> 0;> }> // This code is contributed by Suruchi kumari> |
>
>
C
// A school method based C program to> // check if a number is prime> #include> #include> > // Function check whether a number> // is prime or not> int> isPrime(> int> n)> n % 3 == 0)> > return> 0;> > // Check from 5 to square root of n> > // Iterate i by (i+6)> > for> (> int> i = 5; i * i <= n; i = i + 6)> > if> (n % i == 0> > // Driver Code> int> main()> {> > if> (isPrime(11) == 1)> > printf> (> 'true
'> );> > else> > printf> (> 'false
'> );> > return> 0;> }> // This code is contributed by Suruchi Kumari> |
>
>
Java
// Java program to check whether a number> import> java.lang.*;> import> java.util.*;> > class> GFG {> > > // Function check whether a number> > // is prime or not> > public> static> boolean> isPrime(> int> n)> > > > if> (n <=> 1> )> > return> false> ;> > > // Check if n=2 or n=3> > if> (n ==> 2> > > > // Driver Code> > public> static> void> main(String[] args)> > {> > if> (isPrime(> 11> )) {> > System.out.println(> 'true'> );> > }> > else> {> > System.out.println(> 'false'> );> > }> > }> }> > // This code is contributed by Sayan Chatterjee> |
>
>
Python3
import> math> > def> is_prime(n:> int> )> -> >> bool> :> > > # Check if n=1 or n=0> > if> n <> => 1> :> > return> 'false'> > > # Check if n=2 or n=3> > if> n> => => 2> or> n> => => 3> :> > return> 'true'> > > # Check whether n is divisible by 2 or 3> > if> n> %> 2> => => 0> or> n> %> 3> => => 0> :> > return> 'false'> > > # Check from 5 to square root of n> > # Iterate i by (i+6)> > for> i> in> range> (> 5> ,> int> (math.sqrt(n))> +> 1> ,> 6> ):> > if> n> %> i> => => 0> or> n> %> (i> +> 2> )> => => 0> :> > return> 'false'> > > return> 'true'> > if> __name__> => => '__main__'> :> > print> (is_prime(> 11> ))> |
>
>
C#
pointeur en c
// C# program to check whether a number> using> System;> class> GFG {> > > // Function check whether a number> > // is prime or not> > public> static> bool> isPrime(> int> n)> > > > > // Driver Code> > public> static> void> Main(String[] args)> > {> > if> (isPrime(11)) {> > Console.WriteLine(> 'true'> );> > }> > else> {> > Console.WriteLine(> 'false'> );> > }> > }> }> > // This code is contributed by Abhijeet> // Kumar(abhijeet_19403)> |
>
>
Javascript
// A school method based JS program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> n % (i + 2) == 0)> > return> false> ;> > > return> true> ;> > > // Driver Code> isPrime(11) ? console.log(> 'true'> ) : console.log(> 'false'> );> > > // This code is contributed by phasing17> |
>
>Sortir
true>
Complexité temporelle : O(sqrt(n))
Espace auxiliaire : O(1)
Des solutions efficaces
- Test de primalité | Ensemble 1 (Introduction et méthode scolaire)
- Test de primalité | Ensemble 2 (méthode Fermat)
- Test de primalité | Ensemble 3 (Miller-Rabin)
- Test de primalité | Série 4 (Solovay-Strassen)
- Test de primalité de Lucas
Algorithmes pour trouver tous les nombres premiers plus petits que N.
- Tamis d'Ératosthène
- Tamis d'Eratosthène en complexité temporelle 0(n)
- Tamis segmenté
- Tamis de Sundaram
- Tamis au niveau du bit
- Articles récents sur Sieve !
Plus de problèmes liés au nombre premier
- Trouver deux nombres premiers distincts avec un produit donné
- Imprimer tous les nombres premiers inférieurs ou égaux à N
- Programme récursif pour nombre premier
- Trouver deux nombres premiers avec un somme donnée
- Trouver le chiffre le plus élevé des nombres premiers dans une plage
- Factorisation première utilisant Sieve O (log n) pour plusieurs requêtes
- Programme pour imprimer tous les facteurs premiers d'un nombre donné
- Plus petit facteur premier des nombres jusqu'à n
- Facteurs premiers du LCM des éléments du tableau – techcodeview.com
- Programme pour la conjecture de Goldbach
- Nombres premiers et Fibonacci
- Nombre composé
- Articles récents sur les nombres premiers !