PRVOČÍSLA - TECHCODEVIEW.COM

Čo sú prvočísla?

A prvočíslo je definované ako prirodzené číslo väčšie ako 1 a je deliteľné iba 1 a sebou samým.

Inými slovami, prvočíslo je kladné celé číslo väčšie ako 1, ktoré má práve dva faktory, 1 a samotné číslo. Prvých niekoľko prvočísel je 2, 3, 5, 7, 11, 13, 17, 19, 23. . .

Poznámka: 1 nie je ani prvočíslo, ani zložené. Zostávajúce čísla, okrem 1, sú klasifikované ako prvočísla a zložené čísla.

základné čísla

Niekoľko zaujímavých faktov o prvočíslach:

Okrem 2, ktorá je najmenšia prvočíslo a jediné párne prvočíslo, všetky prvočísla sú nepárne.
Každé prvočíslo môže byť reprezentované vo forme 6n + 1 alebo 6n – 1 okrem prvočísel 2 a 3 , kde n je ľubovoľné prirodzené číslo.
2 a 3 sú len dve po sebe idúce prirodzené čísla, ktoré sú prvočísla.
Goldbachova domnienka: Každé párne celé číslo väčšie ako 2 možno vyjadriť ako súčet dvoch prvočísel.
Wilsonova veta : Wilsonova veta hovorí, že prirodzené číslo p> 1 je prvočíslo vtedy a len vtedy

(p – 1) ! ≡ -1 proti p
ALEBO,
(p – 1) ! ≡ (p-1) mod p

Fermatova malá veta : Ak je n prvočíslo, potom pre každé a platí 1 ≤ a

a ^n-1 ≡ 1 (mod n)
ALEBO,
a ^n-1 % n = 1

Veta o prvom čísle : Pravdepodobnosť, že dané, náhodne zvolené číslo n je prvočíslo, je nepriamo úmerná jeho počtu číslic alebo logaritmu n.
Lemoineova domnienka : Akékoľvek nepárne celé číslo väčšie ako 5 môže byť vyjadrené ako súčet nepárnych prvočísel (všetky prvočísla okrem 2 sú nepárne) a párneho poloprvého čísla. Poloprvočíslo je súčinom dvoch prvočísel. Toto sa nazýva Lemoineova domnienka.

Vlastnosti prvočísel:

Každé číslo väčšie ako 1 možno vydeliť aspoň jedným prvočíslom.
Každé párne kladné celé číslo väčšie ako 2 možno vyjadriť ako súčet dvoch prvočísel.
Okrem 2 sú všetky ostatné prvočísla nepárne. Inými slovami, môžeme povedať, že 2 je jediné párne prvočíslo.
Dve prvočísla sú vždy rovnaké.
Každé zložené číslo môže byť započítané do prvočíselných faktorov a každý z nich je svojou povahou jedinečný.

Prvočísla a vedľajšie prvočísla:

Je dôležité rozlišovať medzi základné čísla a vedľajšie prvočísla . Nižšie sú uvedené rozdiely medzi prvočíslami a vedľajšími prvočíslami.

Prvočísla sa vždy považujú za pár, zatiaľ čo prvočíslo je jedno číslo.
Ko-prvočísla sú čísla, ktoré nemajú žiadny spoločný činiteľ okrem 1. Naproti tomu prvočísla takúto podmienku nemajú.
Ko-prvočíslo môže byť prvočíslo alebo zložené, ale jeho najväčší spoločný faktor (GCF) musí byť vždy 1. Na rozdiel od zložených čísel majú prvočísla iba dva faktory, 1 a samotné číslo.
Príklad co-prime: 13 a 15 sú spoluhlavní. Faktory 13 sú 1 a 13 a faktory 15 sú 1, 3 a 5. Vidíme, že majú len 1 ako spoločný faktor, preto sú to prvočísla.
Príklad prvočísla: Niekoľko príkladov prvočísel je 2, 3, 5, 7 a 11 atď.

Ako skontrolovať, či je číslo prvočíslo alebo nie?

Naivný prístup: Naivný prístup je k

Opakujte od 2 do (n-1) a skontrolujte, či sa nejaké číslo v tomto rozsahu delí n . Ak sa číslo delí n , potom to nie je prvočíslo.

Časová zložitosť: O(N)
Pomocný priestor: O(1)

Naivný prístup (rekurzívny): Rekurzia sa môže použiť aj na kontrolu, či je číslo medzi 2 na n – 1 delí n. Ak nájdeme akékoľvek číslo, ktoré sa delí, vrátime false.

Nižšie je uvedená implementácia vyššie uvedenej myšlienky:

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

Výkon

 false

Časová zložitosť: O(N)
Pomocný priestor: O(N), ak vezmeme do úvahy zásobník rekurzie. V opačnom prípade je to O(1).

Efektívny prístup: Efektívnym riešením je:

Iterujte cez všetky čísla od 2 na druhú odmocninu z n a pre každé číslo skontrolujte, či delí n [pretože ak je číslo vyjadrené ako n = xy a ktorékoľvek z x alebo y je väčšie ako odmocnina z n, druhé musí byť menšie ako odmocnina]. Ak nájdeme akékoľvek číslo, ktoré sa delí, vrátime false.

Nižšie je uvedená implementácia:

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

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

true

Časová zložitosť: O(sqrt(n))
Pomocný priestor: O(1)

Ďalší efektívny prístup: Ak chcete skontrolovať, či je číslo prvočíslo alebo nie, postupujte podľa nižšie uvedeného nápadu:

Budeme sa zaoberať niekoľkými číslami, ako sú 1, 2, 3 a číslami, ktoré sú deliteľné 2 a 3 v samostatných prípadoch a pre ostatné čísla. Iterujte od 5 do sqrt(n) a skontrolujte pre každú iteráciu, či (táto hodnota) alebo (táto hodnota + 2) delí n alebo nie, a zvýšte hodnotu o 6 [pretože každé prvočíslo môže byť vyjadrené ako 6n+1 alebo 6n-1 ]. Ak nájdeme akékoľvek číslo, ktoré sa delí, vrátime false.

Nižšie je uvedená implementácia vyššie 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>

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

Výkon