logo

TechCodeview

Alkuluvut

Mitä ovat alkuluvut?

A alkuluku määritellään luonnolliseksi luvuksi, joka on suurempi kuin 1 ja on jaollinen vain luvulla 1 ja itsellään.

Toisin sanoen alkuluku on positiivinen kokonaisluku, joka on suurempi kuin 1 ja jolla on täsmälleen kaksi tekijää, 1 ja itse luku. Muutamat ensimmäiset alkuluvut ovat 2, 3, 5, 7, 11, 13, 17, 19, 23 . . .



Huomautus: 1 ei ole alkuluku tai yhdistelmä. Loput luvut 1:tä lukuun ottamatta luokitellaan alku- ja yhdistelmäluvuiksi.

alkuluvut

Mielenkiintoisia faktoja alkuluvuista:

  • Paitsi 2, joka on pienin alkuluku ja ainoa parillinen alkuluku, kaikki alkuluvut ovat parittomia lukuja.
  • Jokainen alkuluku voidaan esittää muodossa 6n + 1 tai 6n-1 lukuun ottamatta alkulukuja 2 ja 3 , jossa n on mikä tahansa luonnollinen luku.
  • 2 ja 3 ovat vain kaksi peräkkäistä luonnollista lukua, jotka ovat alkulukuja.
  • Goldbachin olettamus: Jokainen parillinen kokonaisluku, joka on suurempi kuin 2, voidaan ilmaista kahden alkuluvun summana.
  • Wilsonin lause : Wilsonin lause sanoo, että luonnollinen luku p> 1 on alkuluku silloin ja vain jos

(p-1)! ≡ -1 vastaan ​​p
TAI,
(p-1)! ≡ (p-1) mod p



an-1≡ 1 (mod n)
TAI,
an-1% n = 1

  • Alkulukulause : Todennäköisyys, että annettu, satunnaisesti valittu luku n on alkuluku, on kääntäen verrannollinen sen numeroiden lukumäärään tai n:n logaritmiin.
  • Lemoinen arvelu : Mikä tahansa pariton kokonaisluku, joka on suurempi kuin 5, voidaan ilmaista parittoman alkuluvun (kaikki muut kuin 2:n alkuluvut) ja parillisen puolialkuluvun summana. Puolialkuluku on kahden alkuluvun tulo. Tätä kutsutaan Lemoinen olettamukseksi.

Alkulukujen ominaisuudet:

  • Jokainen luku, joka on suurempi kuin 1, voidaan jakaa ainakin yhdellä alkuluvulla.
  • Jokainen parillinen positiivinen kokonaisluku, joka on suurempi kuin 2, voidaan ilmaista kahden alkuluvun summana.
  • Paitsi 2, kaikki muut alkuluvut ovat parittomia. Toisin sanoen voimme sanoa, että 2 on ainoa parillinen alkuluku.
  • Kaksi alkulukua ovat aina toistensa vastalukuja.
  • Jokainen yhdistelmäluku voidaan laskea alkutekijöiksi, ja yksittäin nämä kaikki ovat luonteeltaan ainutlaatuisia.

Alkuluvut ja rinnakkaisalkuluvut:

On tärkeää erottaa toisistaan alkuluvut ja rinnakkaisalkuluvut . Alla on lueteltu erot alkulukujen ja rinnakkaislukujen välillä.

  • Parilukuja pidetään aina parina, kun taas alkuluku on yksi luku.
  • Yhteisalkuluvut ovat lukuja, joilla ei ole yhteistä tekijää paitsi 1. Alkuluvuilla sitä vastoin ei ole tällaista ehtoa.
  • Yhteisalkuluku voi olla joko alkuluku tai yhdistelmä, mutta sen suurimman yhteisen tekijän (GCF) on aina oltava 1. Toisin kuin yhdistelmäluvuissa, alkuluvuilla on vain kaksi tekijää, 1 ja itse luku.
  • Esimerkki yhteisprime:stä: 13 ja 15 ovat rinnakkaislukuja. Tekijät 13 ovat 1 ja 13 ja tekijät 15 ovat 1, 3 ja 5. Näemme, että niillä on vain 1 yhteisenä tekijänä, joten ne ovat koprime-lukuja.
  • Esimerkki alkupäästä: Muutamia esimerkkejä alkuluvuista ovat 2, 3, 5, 7 ja 11 jne.

Kuinka tarkistaa, onko numero ensisijainen vai ei?

Naiivi lähestymistapa: Naiivi lähestymistapa on



Toista 2 arvoon (n-1) ja tarkista, jakaako jokin luku tällä alueella n . Jos luku jakautuu n , silloin se ei ole alkuluku.

Aika monimutkaisuus: PÄÄLLÄ)
Aputila: O(1)

Naiivi lähestymistapa (rekursiivinen): Rekursiota voidaan käyttää myös tarkistamaan, onko luku välillä 2 n:ään – 1 jakaa n:n. Jos löydämme jonkin luvun, joka jakaa, palautetaan epätosi.

Alla yllä olevan idean toteutus:

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> 

>

>

Python 3




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

muhkea tietokonekieli 

>

>

Lähtö 

 false>

Aika monimutkaisuus: PÄÄLLÄ)
Aputila: O(N), jos otetaan huomioon rekursiopino. Muuten se on O(1).

Tehokas lähestymistapa: Tehokas ratkaisu on:

Toista kaikki numerot alkaen 2 neliöjuureen n ja tarkista jokaisen luvun kohdalla, jakaako se n [koska jos luku ilmaistaan ​​muodossa n = xy ja mikä tahansa x tai y on suurempi kuin n:n juuri, toisen on oltava pienempi kuin juuriarvo]. Jos löydämme jonkin luvun, joka jakaa, palautetaan epätosi.

Alla toteutus:

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> 

>

>

Python 3




# 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-kytkin




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

> 
    
 true>

Aika monimutkaisuus: O(sqrt(n))
Aputila: O(1)

Toinen tehokas tapa: Voit tarkistaa, onko luku alkuluku vai ei, seuraa alla olevaa ideaa:

Käsittelemme muutamia lukuja, kuten 1, 2, 3, ja numeroita, jotka ovat jaollisia 2:lla ja 3:lla erillisissä tapauksissa ja jäljellä oleville numeroille. Iteroi arvosta 5 arvoon sqrt(n) ja tarkista jokaisella iteraatiolla, jakaako (tuo arvo) vai (se arvo + 2) n:n vai ei, ja lisää arvoa 6:lla [koska mikä tahansa alkuluku voidaan ilmaista muodossa 6n+1 tai 6n-1 ]. Jos löydämme jonkin luvun, joka jakaa, palautetaan epätosi.

Alla ylläolevan idean toteutus:

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> 

>

>

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> 

>

>

Python 3




import> math> > def> is_prime(n:>int>)>->>>>:> > ># 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#

udp-protokolla




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

>

>

Lähtö 

true>

Aika monimutkaisuus: O(sqrt(n))
Aputila: O(1)

Tehokkaita ratkaisuja

  • Primaliteettitesti | Sarja 1 (johdanto ja koulumenetelmä)
  • Primaliteettitesti | Sarja 2 (Fermat-menetelmä)
  • Primaliteettitesti | Sarja 3 (Miller-Rabin)
  • Primaliteettitesti | Sarja 4 (Solovay-Strassen)
  • Lucasin primiteettitesti

Algoritmit kaikkien N:tä pienempien alkulukujen löytämiseksi.

  • Eratosthenesin seula
  • Eratosthenesin seula 0(n) aikakompleksisuudessa
  • Segmentoitu seula
  • Sundaramin seula
  • Bitwise Seula
  • Uusimmat artikkelit Sievessä!

Lisää alkunumeroon liittyviä ongelmia

  • Etsi kaksi erilaista alkulukua kanssa a annettu tuote
  • Tulosta kaikki alkuluvut, jotka ovat pienempiä tai yhtä suuria kuin N
  • Rekursiivinen ohjelma alkuluvulle
  • Etsi kaksi alkulukua kanssa a annettu summa
  • Etsi alueen suurin alkulukujen luku
  • Prime Factorization käyttämällä Sieve O(log n) -toimintoa useille kyselyille
  • Ohjelma tulostaa tietyn luvun kaikki alkutekijät
  • Lukujen pienin alkutekijä n:ään asti
  • Matriisielementtien LCM:n alkutekijät – techcodeview.com
  • Ohjelma Goldbachin arveluille
  • Alkuluvut ja Fibonacci
  • Yhdistelmänumero
  • Viimeisimmät artikkelit alkuluvuista!