NOMBRES PRIMERS - TECHCODEVIEW.COM

Què són els nombres primers?

A nombre primer es defineix com un nombre natural més gran que 1 i només és divisible per 1 i per si mateix.

En altres paraules, el nombre primer és un nombre enter positiu major que 1 que té exactament dos factors, 1 i el nombre en si. Els primers nombres primers són 2, 3, 5, 7, 11, 13, 17, 19, 23. . .

Nota: 1 no és ni primer ni compost. La resta de nombres, excepte l'1, es classifiquen com a nombres primers i compostos.

nombres primers

Alguns fets interessants sobre els nombres primers:

Excepte 2, que és el més petit nombre primer i l'únic nombre primer parell, tots els nombres primers són nombres senars.
Cada nombre primer es pot representar en forma de 6n + 1 o 6n-1 excepte els nombres primers 2 i 3 , on n és qualsevol nombre natural.
2 i 3 només són dos nombres naturals consecutius primers.
Conjectura de Goldbach: Tot nombre enter parell superior a 2 es pot expressar com la suma de dos primers.
Teorema de Wilson : El teorema de Wilson diu que un nombre natural p> 1 és un nombre primer si i només si

(p – 1) ! ≡ -1 contra p
O,
(p – 1) ! ≡ (p-1) mod pàg

El petit teorema de Fermat : Si n és un nombre primer, aleshores per a cada a, 1 ≤ a

a ^n-1 ≡ 1 (mod n)
O,
a ^n-1 % n = 1

Teorema dels nombres primers : La probabilitat que un nombre donat i escollit aleatòriament n sigui primer és inversament proporcional al seu nombre de dígits, o al logaritme de n.
La conjectura de Lemoine : Qualsevol nombre enter senar superior a 5 es pot expressar com la suma d'un nombre primer senar (tots els nombres primers diferents de 2 són senars) i un semiprim parell. Un nombre semiprim és un producte de dos nombres primers. Això s'anomena conjectura de Lemoine.

Propietats dels nombres primers:

Tot nombre superior a 1 es pot dividir almenys per un nombre primer.
Tot nombre enter parell positiu superior a 2 es pot expressar com la suma de dos primers.
Excepte 2, tots els altres nombres primers són senars. En altres paraules, podem dir que 2 és l'únic nombre primer parell.
Dos nombres primers sempre són copprims entre si.
Cada nombre compost es pot factoritzar en factors primers i, individualment, tots són únics per naturalesa.

Nombres primers i nombres coprims:

És important distingir entre nombres primers i nombres coprims . A continuació es mostren les diferències entre nombres primers i coprims.

Els nombres coprims sempre es consideren un parell, mentre que un nombre primer és un nombre únic.
Els nombres coprims són nombres que no tenen cap factor comú excepte 1. En canvi, els nombres primers no tenen aquesta condició.
Un nombre coprim pot ser primer o compost, però el seu màxim comú divisor (MCF) ha de ser sempre 1. A diferència dels nombres compostos, els nombres primers només tenen dos factors, 1 i el nombre en si.
Exemple de co-prim: 13 i 15 són coprims. Els factors de 13 són 1 i 13 i els factors de 15 són 1, 3 i 5. Podem veure que només tenen 1 com a factor comú, per tant, són nombres copprims.
Exemple de primer: Alguns exemples de nombres primers són 2, 3, 5, 7 i 11, etc.

Com comprovar si un nombre és primer o no?

Enfocament ingenu: L'enfocament ingenu és

Itera de 2 a (n-1) i comprova si algun nombre d'aquest rang es divideix n . Si el nombre es divideix n , aleshores no és un nombre primer.

Complexitat temporal: O(N)
Espai auxiliar: O(1)

Enfocament ingenu (recursiu): La recursivitat també es pot utilitzar per comprovar si hi ha un nombre entre 2 a n – 1 divideix n. Si trobem qualsevol nombre que divideix, retornem fals.

A continuació es mostra la implementació de la idea anterior:

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>

Python 3

# 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.> > >

Sortida

 false

Complexitat temporal: O(N)
Espai auxiliar: O(N) si considerem la pila de recursivitat. En cas contrari, és O(1).

Enfocament eficient: Una solució eficient és:

Recorre tots els números des de 2 a l'arrel quadrada de n i per a cada nombre comproveu si divideix n [perquè si un nombre s'expressa com n = xy i qualsevol de les x o y és més gran que l'arrel de n, l'altre ha de ser menor que el valor de l'arrel]. Si trobem qualsevol nombre que divideix, retornem fals.

A continuació es mostra la implementació:

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>

Python 3

# 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

// 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.  ?>>

Sortida

true

Complexitat temporal: O(sqrt(n))
Espai auxiliar: O(1)

Un altre enfocament eficient: Per comprovar si el nombre és primer o no, seguiu la següent idea:

Tractarem uns quants nombres com 1, 2, 3 i els nombres que són divisibles per 2 i 3 en casos separats i per als nombres restants. Itereu de 5 a sqrt(n) i comproveu per a cada iteració si (aquest valor) o (aquest valor + 2) divideix n o no i augmenta el valor en 6 [perquè qualsevol nombre primer es pot expressar com 6n+1 o 6n-1 ]. Si trobem qualsevol nombre que divideix, retornem fals.

A continuació es mostra la implementació de la idea anterior:

C++

'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>

Python 3

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#

// 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>

Sortida