Kaj so praštevila?
A praštevilo je definirano kot naravno število, večje od 1 in je deljiva samo z 1 in samim seboj.
Z drugimi besedami, praštevilo je pozitivno celo število, večje od 1, ki ima natanko dva faktorja, 1 in samo število. Prvih nekaj praštevil je 2, 3, 5, 7, 11, 13, 17, 19, 23. . .
Opomba: 1 ni niti praštevilna niti sestavljena. Preostala števila, razen 1, so razvrščena kot praštevila in sestavljena števila.

praštevila
Nekaj zanimivih dejstev o praštevilih:
- Razen 2, ki sta najmanjša praštevilo in edino sodo praštevilo, so vsa praštevila liha števila.
- Vsako praštevilo je mogoče predstaviti v obliki 6n + 1 oz 6n – 1 razen praštevil 2 in 3 , kjer je n poljubno naravno število.
- 2 in 3 sta samo dve zaporedni naravni števili, ki sta praštevili.
- Goldbachova domneva: Vsako sodo celo število, večje od 2, je mogoče izraziti kot vsoto dveh praštevil.
- Wilsonov izrek : Wilsonov izrek pravi, da je naravno število p> 1 praštevilo, če in samo če
(p – 1) ! ≡ -1 proti p
ALI,
(p – 1) ! ≡ (p-1) mod str
- Fermatov mali izrek : Če je n praštevilo, potem za vsak a velja 1 ≤ a
an-1≡ 1 (mod n)
ALI,
an-1% n = 1
- Izrek o praštevilu : Verjetnost, da je dano, naključno izbrano število n praštevilo, je obratno sorazmerna z njegovim številom števk ali z logaritmom števila n.
- Lemoinova domneva : Vsako liho celo število, večje od 5, je mogoče izraziti kot vsoto lihega praštevila (vsa praštevila razen 2 so liha) in sodega polpraštevila. Polpraštevilo je produkt dveh praštevil. To se imenuje Lemoinova domneva.
Lastnosti praštevil:
- Vsako število, večje od 1, je mogoče deliti z vsaj enim praštevilom.
- Vsako sodo pozitivno celo število, večje od 2, je mogoče izraziti kot vsoto dveh praštevil.
- Razen 2 so vsa praštevila liha. Z drugimi besedami, lahko rečemo, da je 2 edino sodo praštevilo.
- Dve praštevili sta med seboj vedno enaki.
- Vsako sestavljeno število je mogoče faktorizirati na prafaktorje in vsi posamično so edinstveni.
Praštevila in sopraštevila:
Pomembno je razlikovati med praštevila in sopraštevila . Spodaj so navedene razlike med praštevili in sopraštevili.
- Kopraštevila se vedno obravnavajo kot par, medtem ko je praštevilo eno samo število.
- Enako praštevila so števila, ki nimajo skupnega faktorja razen 1. Nasprotno pa praštevila nimajo takega pogoja.
- Enako praštevilo je lahko praštevilo ali sestavljeno, vendar mora biti njegov največji skupni faktor (GCF) vedno 1. Za razliko od sestavljenih števil imajo praštevila samo dva faktorja, 1 in samo število.
- Primer soprime: 13 in 15 je sopraštevil. Faktorji števila 13 so 1 in 13, faktorji števila 15 pa 1, 3 in 5. Vidimo lahko, da imajo samo 1 skupni faktor, torej so sopraštevili.
- Primer prime: Nekaj primerov praštevil je 2, 3, 5, 7 in 11 itd.
Kako preveriti, ali je številka Pra ali ne?
Naivni pristop: Naiven pristop je
Ponavljajte od 2 do (n-1) in preverite, ali se katera koli številka v tem območju deli n . Če se število deli n , potem to ni praštevilo.
Časovna zapletenost: O(N)
Pomožni prostor: O(1)
Naivni pristop (rekurziven): Rekurzijo lahko uporabite tudi za preverjanje, ali je število med 2 na n – 1 deli n. Če najdemo katero koli število, ki se deli, vrnemo false.
Spodaj je izvedba zgornje ideje:
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.> > > |
če drugače v lupini bash
>
>Izhod
false>
Časovna zapletenost: O(N)
Pomožni prostor: O(N), če upoštevamo rekurzivni sklad. V nasprotnem primeru je O(1).
Učinkovit pristop: Učinkovita rešitev je:
Preberi vse številke iz 2 na kvadratni koren iz n in za vsako število preverite, ali deli n [ker če je število izraženo kot n = xy in kateri koli od x ali y je večji od korena n, drugi mora biti manjši od korenske vrednosti]. Če najdemo katero koli število, ki se deli, vrnemo false.
Spodaj je izvedba:
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
kaj je orakelj
// 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. ?>> |
>
>Izhod
true>
Časovna zapletenost: O(sqrt(n))
Pomožni prostor: O(1)
Drug učinkovit pristop: Če želite preveriti, ali je število praštevilo ali ne, sledite spodnji zamisli:
Obravnavali bomo nekaj števil, kot so 1, 2, 3, in števila, ki so deljiva z 2 in 3 v ločenih primerih in za preostala števila. Ponovite od 5 do sqrt(n) in za vsako ponovitev preverite, ali (ta vrednost) ali (ta vrednost + 2) deli n ali ne, in povečajte vrednost za 6 [ker je vsako praštevilo mogoče izraziti kot 6n+1 ali 6n-1 ]. Če najdemo katero koli število, ki se deli, vrnemo false.
Spodaj je izvedba zgornje zamisli:
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> |
abstraktni razred proti vmesniku
>
>
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> |
>
>Izhod
true>
Časovna zahtevnost: O(sqrt(n))
Pomožni prostor: O(1)
Učinkovite rešitve
- Preizkus primanosti | 1. sklop (uvod in šolska metoda)
- Preizkus primanosti | 2. sklop (metoda Fermat)
- Preizkus primanosti | 3. niz (Miller–Rabin)
- Preizkus primanosti | Komplet 4 (Solovay-Strassen)
- Lucasov test prvotnosti
Algoritmi za iskanje vseh praštevil, manjših od N.
- Eratostenovo sito
- Eratostenovo sito v 0(n) časovni zahtevnosti
- Segmentirano sito
- Sito Sundaram
- Bitno sito
- Nedavni članki o situ!
Več težav, povezanih s praštevilom
- Poiščite dve različni praštevili z a dani izdelek
- Izpišite vsa praštevila, manjša ali enaka N
- Rekurzivni program za praštevilo
- Poiščite dve praštevili z a podana vsota
- Poiščite najvišjo števko v praštevilih v obsegu
- Prafaktorizacija z uporabo sita O(log n) za več poizvedb
- Program za izpis vseh prafaktorjev danega števila
- Najmanjši prafaktor števil do n
- Prafaktorji LCM elementov polja – techcodeview.com
- Program za Goldbachovo domnevo
- Praštevila in Fibonacci
- Sestavljeno število
- Najnovejši članki o praštevilih!