PRVOČÍSLA - TECHCODEVIEW.COM

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

Fermatova malá věta : Jestliže n je prvočíslo, pak pro každé a, 1 ≤ a

A^n-1≡ 1 (mod n)
NEBO,
A^n-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++

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