logo

TechCodeview

Numeri primi

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

UNn-1≡ 1 (mod n)
O,
UNn-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.> >>

rimuovi il primo carattere excel 

>

>

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

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

>

>

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




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

>

>

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


Java contiene una sottostringa



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

true>

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

Soluzioni efficienti

  • Test di primalità | Set 1 (Introduzione e metodo scolastico)
  • Test di primalità | Set 2 (metodo Fermat)
  • Test di primalità | Serie 3 (Miller-Rabin)
  • Test di primalità | Set 4 (Solovay-Strassen)
  • Test della primalità di Lucas

Algoritmi per trovare tutti i numeri primi minori di N.

  • Setaccio di Eratostene
  • Crivello di Eratostene con complessità temporale 0(n).
  • Setaccio segmentato
  • Setaccio di Sundaram
  • Setaccio bit a bit
  • Articoli recenti su Sieve!

Ancora problemi legati al numero Prime

  • Trova due numeri primi distinti con UN dato prodotto
  • Stampa tutti i numeri primi minori o uguali a N
  • Programma ricorsivo per numeri primi
  • Trova due numeri primi con UN data somma
  • Trova la cifra più alta tra i numeri primi in un intervallo
  • Fattorizzazione prima utilizzando Sieve O(log n) per query multiple
  • Programma per stampare tutti i fattori primi di un dato numero
  • Fattore primo dei numeri fino a n
  • Fattori primi di LCM di elementi di array – techcodeview.com
  • Programma per la congettura di Goldbach
  • Numeri primi e Fibonacci
  • Numero composto
  • Articoli recenti sui numeri primi!