logo

TechCodeview

Numere prime

Ce sunt numerele prime?

A număr prim este definit ca un număr natural mai mare decât 1 și este divizibil doar cu 1 și cu el însuși.

Cu alte cuvinte, numărul prim este un număr întreg pozitiv mai mare decât 1 care are exact doi factori, 1 și numărul însuși. Primele numere prime sunt 2, 3, 5, 7, 11, 13, 17, 19, 23. . .



Notă: 1 nu este nici prim, nici compus. Numerele rămase, cu excepția lui 1, sunt clasificate ca numere prime și numere compuse.

numere prime

Câteva fapte interesante despre numerele prime:

  • Cu excepția lui 2, care este cel mai mic număr prim și singurul număr prim par, toate numerele prime sunt numere impare.
  • Fiecare număr prim poate fi reprezentat sub formă de 6n + 1 sau 6n – 1 cu excepția numerelor prime 2 și 3 , unde n este orice număr natural.
  • 2 și 3 sunt doar două numere naturale consecutive care sunt prime.
  • Conjectura Goldbach: Fiecare număr întreg par mai mare de 2 poate fi exprimat ca suma a două numere prime.
  • Teorema Wilson : Teorema lui Wilson afirmă că un număr natural p> 1 este un număr prim dacă și numai dacă

(p – 1) ! ≡ -1 față de p
SAU,
(p – 1) ! ≡ (p-1) mod p



An-1≡ 1 (mod n)
SAU,
An-1% n = 1

  • Teorema numărului prim : Probabilitatea ca un număr dat, ales aleatoriu, n să fie prim este invers proporțională cu numărul său de cifre sau cu logaritmul lui n.
  • Conjectura lui Lemoine : Orice număr întreg impar mai mare de 5 poate fi exprimat ca o sumă a unui prim impar (toate numerele prime, altele decât 2, sunt impare) și a unui semiprim par. Un număr semiprim este un produs a două numere prime. Aceasta se numește conjectura lui Lemoine.

Proprietățile numerelor prime:

  • Fiecare număr mai mare decât 1 poate fi împărțit la cel puțin un număr prim.
  • Fiecare număr întreg pozitiv egal mai mare de 2 poate fi exprimat ca suma a două numere prime.
  • Cu excepția lui 2, toate celelalte numere prime sunt impare. Cu alte cuvinte, putem spune că 2 este singurul număr prim par.
  • Două numere prime sunt întotdeauna coprime unul față de celălalt.
  • Fiecare număr compus poate fi factorizat în factori primi și, individual, toți aceștia sunt unici în natură.

Numere prime și numere coprime:

Este important să se facă distincția între numere prime și numere coprime . Mai jos sunt enumerate diferențele dintre numerele prime și coprime.

  • Numerele coprime sunt întotdeauna considerate ca o pereche, în timp ce un număr prim este un singur număr.
  • Numerele coprime sunt numere care nu au un factor comun cu excepția 1. În schimb, numerele prime nu au o astfel de condiție.
  • Un număr coprim poate fi fie prim, fie compus, dar cel mai mare factor comun al său (GCF) trebuie să fie întotdeauna 1. Spre deosebire de numerele compuse, numerele prime au doar doi factori, 1 și numărul însuși.
  • Exemplu de coprim: 13 iar 15 sunt coprime. Factorii lui 13 sunt 1 și 13, iar factorii lui 15 sunt 1, 3 și 5. Putem vedea că au doar 1 ca factor comun, prin urmare, sunt numere coprime.
  • Exemplu de prim: Câteva exemple de numere prime sunt 2, 3, 5, 7 și 11 etc.

Cum se verifică dacă un număr este prim sau nu?

Abordare naivă: Abordarea naivă este de a



Repetați de la 2 la (n-1) și verificați dacă vreun număr din acest interval se împarte n . Dacă numărul se împarte n , atunci nu este un număr prim.

Complexitatea timpului: PE)
Spațiu auxiliar: O(1)

Abordare naivă (recursivă): Recursiunea poate fi folosită și pentru a verifica dacă un număr între 2 la n – 1 împarte n. Dacă găsim orice număr care împarte, returnăm fals.

Mai jos este implementarea ideii de mai sus:

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

când începe q2 

>

>

Ieșire 

 false>

Complexitatea timpului: PE)
Spațiu auxiliar: O(N) dacă luăm în considerare stiva de recursivitate. În caz contrar, este O(1).

Abordare eficientă: O soluție eficientă este:

Iterați prin toate numerele de la 2 la rădăcina pătrată a n iar pentru fiecare număr verificați dacă împarte n [pentru că dacă un număr este exprimat ca n = xy și oricare dintre x sau y este mai mare decât rădăcina lui n, celălalt trebuie să fie mai mic decât valoarea rădăcinii]. Dacă găsim orice număr care împarte, returnăm fals.

Mai jos este implementarea:

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

ce este oracolul




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

> 
    
 true>

Complexitatea timpului: O(sqrt(n))
Spatiu auxiliar: O(1)

O altă abordare eficientă: Pentru a verifica dacă numărul este prim sau nu, urmați ideea de mai jos:

Ne vom ocupa de câteva numere precum 1, 2, 3 și de numerele care sunt divizibile cu 2 și 3 în cazuri separate și pentru numerele rămase. Iterați de la 5 la sqrt(n) și verificați pentru fiecare iterație dacă (aceasta valoare) sau (aceasta valoare + 2) împarte n sau nu și creșteți valoarea cu 6 [pentru că orice prim poate fi exprimat ca 6n+1 sau 6n-1 ]. Dacă găsim orice număr care împarte, returnăm fals.

Mai jos este implementarea ideii de mai sus:

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>)>->>>>>:> > ># 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


harald baldr



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

>

>

Ieșire 

true>

Complexitatea timpului: O(sqrt(n))
Spatiu auxiliar: O(1)

Soluții eficiente

  • Test de primalitate | Setul 1 (Introducere și Metoda școlii)
  • Test de primalitate | Set 2 (Metoda Fermat)
  • Test de primalitate | Setul 3 (Miller–Rabin)
  • Test de primalitate | Setul 4 (Solovay-Strassen)
  • Testul de primalitate Lucas

Algoritmi pentru a găsi toate numerele prime mai mici decât N.

  • Sita lui Eratosthenes
  • Sita lui Eratosthenes în complexitate de timp 0(n).
  • Sita segmentata
  • Sita de Sundaram
  • Sită pe biți
  • Articole recente despre Sieve!

Mai multe probleme legate de numărul prim

  • Găsiți două numere prime distincte cu A produs dat
  • Tipăriți toate numerele prime mai mici sau egale cu N
  • Program recursiv pentru numărul prim
  • Găsiți două numere prime cu A suma dată
  • Găsiți cea mai mare cifră care apare în numere prime dintr-un interval
  • Factorizarea primă folosind Sieve O(log n) pentru mai multe interogări
  • Program pentru a tipări toți factorii primi ai unui număr dat
  • Cel mai mic factor prim al numerelor până la n
  • Factorii primi ai LCM ai elementelor de matrice – techcodeview.com
  • Program pentru Conjectura lui Goldbach
  • Numerele prime și Fibonacci
  • Numar compus
  • Articole recente despre numerele prime!