logo

TechCodeview

Praštevila

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



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!