ALKUNUMEROT - TECHCODEVIEW.COM

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

Fermatin pieni lause : Jos n on alkuluku, niin jokaisella a:lla 1 ≤ a

a ^n-1 ≡ 1 (mod n)
TAI,
a ^n-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.> > >

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

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

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