logo

Prvočísla

Co jsou prvočísla?

A prvočíslo je definováno jako přirozené číslo větší než 1 a je dělitelný pouze 1 a sebou samým.

Jinými slovy, prvočíslo je kladné celé číslo větší než 1, které má právě dva faktory, 1 a samotné číslo. Prvních několik prvočísel je 2, 3, 5, 7, 11, 13, 17, 19, 23. . .



Poznámka: 1 není prvočíslo ani složené. Zbývající čísla, kromě 1, jsou klasifikována jako prvočísla a složená čísla.

prvočísla

Několik zajímavých faktů o prvočíslech:

  • Kromě 2, která je nejmenší prvočíslo a jediné sudé prvočíslo, všechna prvočísla jsou lichá.
  • Každé prvočíslo může být reprezentováno ve tvaru 6n + 1 nebo 6n – 1 kromě prvočísel 2 a 3 , kde n je libovolné přirozené číslo.
  • 2 a 3 jsou pouze dvě po sobě jdoucí přirozená čísla, která jsou prvočísla.
  • Goldbachova domněnka: Každé sudé celé číslo větší než 2 lze vyjádřit jako součet dvou prvočísel.
  • Wilsonova věta : Wilsonova věta říká, že přirozené číslo p> 1 je prvočíslo právě tehdy a jen tehdy

(p – 1)! ≡ -1 proti str
NEBO,
(p – 1)! ≡ (p-1) mod p



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

  • Věta o prvočíslech : Pravděpodobnost, že dané, náhodně zvolené číslo n je prvočíslo, je nepřímo úměrná jeho počtu číslic nebo logaritmu n.
  • Lemoineova domněnka : Libovolné liché celé číslo větší než 5 lze vyjádřit jako součet lichých prvočísel (všechna prvočísla kromě 2 jsou lichá) a sudého poloprvého čísla. Poloprvočíslo je součinem dvou prvočísel. Tomu se říká Lemoineova domněnka.

Vlastnosti prvočísel:

  • Každé číslo větší než 1 lze vydělit alespoň jedním prvočíslem.
  • Každé sudé kladné celé číslo větší než 2 lze vyjádřit jako součet dvou prvočísel.
  • Kromě 2 jsou všechna ostatní prvočísla lichá. Jinými slovy, můžeme říci, že 2 je jediné sudé prvočíslo.
  • Dvě prvočísla jsou vždy souběžná.
  • Každé složené číslo lze rozdělit na prvočinitele a jednotlivě jsou všechny svou povahou jedinečné.

Prvočísla a vedlejší prvočísla:

Je důležité rozlišovat mezi prvočísla a vedlejší prvočísla . Níže jsou uvedeny rozdíly mezi prvočísly a vedlejšími prvočísly.

  • Prvočísla jsou vždy považována za pár, zatímco prvočíslo je jediné číslo.
  • Vedlejší prvočísla jsou čísla, která nemají žádný společný faktor kromě 1. Naproti tomu prvočísla takovou podmínku nemají.
  • Společné prvočíslo může být prvočíslo nebo složené, ale jeho největší společný faktor (GCF) musí být vždy 1. Na rozdíl od složených čísel mají prvočísla pouze dva faktory, 1 a samotné číslo.
  • Příklad co-prime: 13 a 15 jsou co-primes. Faktory 13 jsou 1 a 13 a faktory 15 jsou 1, 3 a 5. Vidíme, že mají jako společný faktor pouze 1, jsou to tedy prvočísla.
  • Příklad prvočísla: Několik příkladů prvočísel je 2, 3, 5, 7 a 11 atd.

Jak zkontrolovat, zda je číslo prvočíslo nebo ne?

Naivní přístup: Naivní přístup je k



Opakujte od 2 do (n-1) a zkontrolujte, zda se nějaké číslo v tomto rozsahu dělí n . Pokud se číslo dělí n , pak to není prvočíslo.

Časová náročnost: NA)
Pomocný prostor: O(1)

Naivní přístup (rekurzivní): Rekurzi lze také použít ke kontrole, zda je číslo mezi 2 na n – 1 dělí n. Pokud najdeme nějaké číslo, které se dělí, vrátíme false.

Níže je uvedena implementace výše uvedené myšlenky:

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>

>

>

Jáva




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

přejmenování adresáře linux

>

>

Výstup

 false>

Časová náročnost: NA)
Pomocný prostor: O(N), pokud vezmeme v úvahu zásobník rekurze. Jinak je to O(1).

Efektivní přístup: Efektivní řešení je:

Iterujte přes všechna čísla od 2 na druhou odmocninu n a pro každé číslo zkontrolujte, zda dělí n [protože je-li číslo vyjádřeno jako n = xy a kterékoli z x nebo y je větší než odmocnina z n, druhé musí být menší než odmocnina]. Pokud najdeme nějaké číslo, které se dělí, vrátíme false.

Níže je implementace:

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

>

>

Jáva




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

java hashset




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

>

>

Výstup

true>

Časová náročnost: O(sqrt(n))
Pomocný prostor: O(1)

Další efektivní přístup: Chcete-li zkontrolovat, zda je číslo prvočíslo nebo ne, postupujte podle níže uvedeného nápadu:

Budeme se zabývat několika čísly jako 1, 2, 3 a čísly, která jsou dělitelná 2 a 3 v samostatných případech a pro zbývající čísla. Iterujte od 5 do sqrt(n) a pro každou iteraci zkontrolujte, zda (tato hodnota) nebo (tato hodnota + 2) dělí n nebo ne, a zvyšte hodnotu o 6 [protože jakékoli prvočíslo lze vyjádřit jako 6n+1 nebo 6n-1 ]. Pokud najdeme nějaké číslo, které se dělí, vrátíme false.

Níže je uvedena implementace výše uvedeného nápadu:

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>

>

>

Jáva




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

>

>

kat timpf výška
Výstup

true>

Časová složitost: O(sqrt(n))
Pomocný prostor: O(1)

Efektivní řešení

  • Test primality | Sada 1 (Úvod a školní metoda)
  • Test primality | Sada 2 (metoda Fermat)
  • Test primality | Sada 3 (Miller–Rabin)
  • Test primality | Sada 4 (Solovay-Strassen)
  • Lucasův test primality

Algoritmy k nalezení všech prvočísel menších než N.

  • Eratosthenovo síto
  • Eratosthenovo síto v 0(n) časové složitosti
  • Segmentované síto
  • Síto Sundaram
  • Bitové síto
  • Nedávné články o Sieve!

Další problémy související s prvočíslem

  • Najděte dvě odlišná prvočísla s A daný produkt
  • Vytiskněte všechna prvočísla menší nebo rovna N
  • Rekurzivní program pro prvočíslo
  • Najděte dvě prvočísla s A daná suma
  • Najděte nejvyšší vyskytující se číslici v prvočíslech v rozsahu
  • Primární faktorizace pomocí Sieve O (log n) pro více dotazů
  • Program pro tisk všech prvočísel daného čísla
  • Nejmenší prvočinitel čísel do n
  • Primární faktory LCM prvků pole – techcodeview.com
  • Program pro Goldbachovu domněnku
  • Prvočísla a Fibonacciho
  • Složené číslo
  • Nejnovější články o prvočíslech!