NUMERI PRIMI - TECHCODEVIEW.COM

Cosa sono i numeri primi?

UN numero primo è definito come un numero naturale maggiore di 1 ed è divisibile solo per 1 e per se stesso.

In altre parole, il numero primo è un intero positivo maggiore di 1 che ha esattamente due fattori, 1 e il numero stesso. I primi numeri primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23 . . .

Nota: 1 non è né primo né composito. I restanti numeri, tranne 1, sono classificati come numeri primi e composti.

numeri primi

Alcuni fatti interessanti sui numeri primi:

Tranne 2, che è il più piccolo numero primo e l'unico numero primo pari, tutti i numeri primi sono numeri dispari.
Ogni numero primo può essere rappresentato sotto forma di 6n+1 O 6n-1 tranne i numeri primi 2 E 3 , dove n è un numero naturale qualsiasi.
2 e 3 ci sono solo due numeri naturali consecutivi che sono primi.
Congettura di Goldbach: Ogni intero pari maggiore di 2 può essere espresso come la somma di due numeri primi.
Teorema di Wilson : Il teorema di Wilson afferma che un numero naturale p> 1 è un numero primo se e solo se

(p-1) ! ≡ -1 contro p
O,
(p-1) ! ≡ (p-1) mod p

Il piccolo teorema di Fermat : Se n è un numero primo, allora per ogni a, 1 ≤ a

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

Teorema dei numeri primi : La probabilità che un dato numero n scelto casualmente sia primo è inversamente proporzionale al suo numero di cifre, o al logaritmo di n.
La congettura di Lemoine : Qualsiasi numero intero dispari maggiore di 5 può essere espresso come somma di un primo dispari (tutti i numeri primi diversi da 2 sono dispari) e di un semiprimo pari. Un numero semiprimo è il prodotto di due numeri primi. Questa è chiamata congettura di Lemoine.

Proprietà dei numeri primi:

Ogni numero maggiore di 1 può essere diviso per almeno un numero primo.
Ogni intero positivo pari maggiore di 2 può essere espresso come la somma di due numeri primi.
Tranne 2, tutti gli altri numeri primi sono dispari. In altre parole, possiamo dire che 2 è l’unico numero primo pari.
Due numeri primi sono sempre coprimi tra loro.
Ogni numero composto può essere scomposto in fattori primi e individualmente tutti questi sono unici in natura.

Numeri primi e numeri coprimi:

È importante distinguere tra numeri primi E numeri coprimi . Di seguito sono elencate le differenze tra numeri primi e coprimi.

I numeri coprime sono sempre considerati come una coppia, mentre un numero primo è un numero singolo.
I numeri coprimi sono numeri che non hanno alcun fattore comune tranne 1. Al contrario, i numeri primi non hanno tale condizione.
Un numero coprimo può essere primo o composto, ma il suo massimo comun divisore (GCF) deve sempre essere 1. A differenza dei numeri composti, i numeri primi hanno solo due fattori, 1 e il numero stesso.
Esempio di coprimo: 13 e 15 sono coprimi. I divisori di 13 sono 1 e 13 e i divisori di 15 sono 1, 3 e 5. Possiamo vedere che hanno solo 1 come divisore comune, quindi sono numeri coprimi.
Esempio di primo: Alcuni esempi di numeri primi sono 2, 3, 5, 7 e 11 ecc.

Come verificare se un numero è Prime o no?

Approccio ingenuo: L'approccio ingenuo è quello di

Scorrere da 2 a (n-1) e controllare se qualche numero in questo intervallo si divide N . Se il numero si divide N , allora non è un numero primo.

Complessità temporale: SU)
Spazio ausiliario: O(1)

Approccio ingenuo (ricorsivo): La ricorsione può essere utilizzata anche per verificare se un numero compreso tra 2 a n – 1 divide n. Se troviamo un numero che divide, restituiamo false.

Di seguito è riportata l'implementazione dell'idea di cui sopra:

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>

Giava

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

Produzione

 false

Complessità temporale: SU)
Spazio ausiliario: O(N) se consideriamo lo stack di ricorsione. Altrimenti è O(1).

Approccio efficiente: Una soluzione efficiente è:

Scorri tutti i numeri da 2 alla radice quadrata di N e per ogni numero controlla se divide n [perché se un numero è espresso come n = xy e uno qualsiasi dei valori x o y è maggiore della radice di n, l'altro deve essere inferiore al valore della radice]. Se troviamo un numero che divide, restituiamo false.

Di seguito l'implementazione:

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;> }>

Giava

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

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

Produzione

true

Complessità temporale: O(quadrato(n))
Spazio ausiliario: O(1)

Un altro approccio efficiente: Per verificare se il numero è primo o meno, segui l'idea seguente:

Tratteremo alcuni numeri come 1, 2, 3 e i numeri divisibili per 2 e 3 in casi separati e per i numeri rimanenti. Itera da 5 a sqrt(n) e controlla per ogni iterazione se (quel valore) o (quel valore + 2) divide n o no e incrementa il valore di 6 [perché qualsiasi numero primo può essere espresso come 6n+1 o 6n-1 ]. Se troviamo un numero che divide, restituiamo false.

Di seguito è riportata l'implementazione dell'idea di cui sopra:

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>

Giava

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

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

Produzione