logo

TechCodeview

Pirminiai skaičiai

Kas yra pirminiai skaičiai?

A pirminis skaičius apibrėžiamas kaip natūralusis skaičius, didesnis nei 1 ir dalijasi tik iš 1 ir savęs.

Kitaip tariant, pirminis skaičius yra teigiamas sveikasis skaičius, didesnis nei 1, turintis lygiai du veiksnius: 1 ir patį skaičių. Pirmieji keli pirminiai skaičiai yra 2, 3, 5, 7, 11, 13, 17, 19, 23. . .



Pastaba: 1 nėra nei pirminis, nei sudėtinis. Likę skaičiai, išskyrus 1, skirstomi į pirminius ir sudėtinius skaičius.

pirminiai skaičiai

Keletas įdomių faktų apie pirminius skaičius:

  • Išskyrus 2, kurie yra mažiausi pirminis skaičius ir vienintelis lyginis pirminis skaičius, visi pirminiai skaičiai yra nelyginiai.
  • Kiekvienas pirminis skaičius gali būti pavaizduotas forma 6n + 1 arba 6n – 1 išskyrus pirminius skaičius 2 ir 3 , kur n yra bet koks natūralusis skaičius.
  • 2 ir 3 yra tik du iš eilės pirminiai natūralūs skaičiai.
  • Goldbacho spėjimas: Kiekvienas lyginis sveikasis skaičius, didesnis nei 2, gali būti išreikštas dviejų pirminių skaičių suma.
  • Vilsono teorema : Wilsono teorema teigia, kad natūralusis skaičius p> 1 yra pirminis skaičius tada ir tik tada, kai

(p – 1) ! ≡ -1 prieš p
ARBA,
(p – 1) ! ≡ (p-1) mod p



an-1≡ 1 (mod. n)
ARBA,
an-1% n = 1

  • Pirminio skaičiaus teorema : Tikimybė, kad duotas atsitiktinai pasirinktas skaičius n yra pirminis, yra atvirkščiai proporcinga jo skaitmenų skaičiui arba n logaritmui.
  • Lemoine'o spėjimas : Bet koks nelyginis sveikasis skaičius, didesnis nei 5, gali būti išreikštas kaip nelyginio pirminio (visi pirminiai skaičiai, išskyrus 2, yra nelyginiai) ir lyginio puspirminio skaičiaus suma. Pusiau pirminis skaičius yra dviejų pirminių skaičių sandauga. Tai vadinama Lemoine'o spėjimu.

Pirminių skaičių savybės:

  • Kiekvienas skaičius, didesnis nei 1, gali būti padalintas iš bent vieno pirminio skaičiaus.
  • Kiekvienas lyginis teigiamas sveikasis skaičius, didesnis nei 2, gali būti išreikštas dviejų pirminių skaičių suma.
  • Išskyrus 2, visi kiti pirminiai skaičiai yra nelyginiai. Kitaip tariant, galime pasakyti, kad 2 yra vienintelis lyginis pirminis skaičius.
  • Du pirminiai skaičiai visada yra vienas kito pirminiai skaičiai.
  • Kiekvienas sudėtinis skaičius gali būti įtrauktas į pirminius veiksnius ir visi jie yra unikalūs.

Pirminiai skaičiai ir pirminiai skaičiai:

Svarbu atskirti pirminiai skaičiai ir kopirminiai skaičiai . Žemiau pateikiami pirminių ir bendro pirminių skaičių skirtumai.

  • Pirminiai skaičiai visada laikomi pora, o pirminis skaičius yra vienas skaičius.
  • Bendri pirminiai skaičiai yra skaičiai, kurie neturi bendro koeficiento, išskyrus 1. Priešingai, pirminiai skaičiai neturi tokios sąlygos.
  • Bendras pirminis skaičius gali būti pirminis arba sudėtinis, tačiau jo didžiausias bendras koeficientas (GCF) visada turi būti 1. Skirtingai nuo sudėtinių skaičių, pirminiai skaičiai turi tik du veiksnius: 1 ir patį skaičių.
  • Bendro primimo pavyzdys: 13 ir 15 yra kopirminiai. 13 koeficientai yra 1 ir 13, o 15 koeficientai yra 1, 3 ir 5. Matome, kad jų bendras koeficientas yra tik 1, todėl jie yra pirminiai skaičiai.
  • Pirminio pavyzdys: Keletas pirminių skaičių pavyzdžių yra 2, 3, 5, 7 ir 11 ir kt.

Kaip patikrinti, ar skaičius yra pagrindinis, ar ne?

Naivus požiūris: Naivus požiūris į



Pakartokite nuo 2 iki (n-1) ir patikrinkite, ar kuris nors skaičius šiame diapazone dalijasi n . Jei skaičius dalijasi n , tada tai nėra pirminis skaičius.

Laiko sudėtingumas: O(N)
Pagalbinė erdvė: O(1)

Naivus požiūris (rekursyvus): Rekursija taip pat gali būti naudojama norint patikrinti, ar skaičius tarp 2 į n – 1 dalijasi n. Jei randame bet kurį skaičių, kuris dalijasi, grąžinsime false.

Žemiau pateikiamas aukščiau pateiktos idėjos įgyvendinimas:

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

metodų sąrašas java 

>

>

Išvestis 

 false>

Laiko sudėtingumas: O(N)
Pagalbinė erdvė: O(N), jei atsižvelgsime į rekursijos krūvą. Kitu atveju tai yra O(1).

Efektyvus požiūris: Veiksmingas sprendimas yra:

Pakartokite visus skaičius nuo 2 į kvadratinę šaknį n ir kiekvienam skaičiui patikrinkite, ar jis dalijasi n [nes jei skaičius išreiškiamas kaip n = xy ir bet kuris iš x arba y yra didesnis už n šaknį, kitas turi būti mažesnis už šaknies reikšmę]. Jei randame bet kurį skaičių, kuris dalijasi, grąžinsime false.

Žemiau pateikiamas įgyvendinimas:

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

java žemėlapiai




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

Laiko sudėtingumas: O(sqrt(n))
Pagalbinė erdvė: O(1)

Kitas efektyvus metodas: Norėdami patikrinti, ar skaičius yra pirminis, ar ne, vadovaukitės toliau pateikta idėja:

Mes nagrinėsime keletą skaičių, tokių kaip 1, 2, 3, ir skaičius, kurie dalijasi iš 2 ir 3, atskirais atvejais ir likusius skaičius. Pakartokite nuo 5 iki sqrt(n) ir kiekvieną kartą patikrinkite, ar (ta reikšmė) arba (ta reikšmė + 2) dalijasi n, ar ne, ir padidinkite vertę 6 [nes bet koks pirminis dydis gali būti išreikštas kaip 6n+1 arba 6n-1 ]. Jei randame bet kurį skaičių, kuris dalijasi, grąžinsime false.

Žemiau pateikiamas aukščiau pateiktos idėjos įgyvendinimas:

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> 

>

>

Python3




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

>

>

kiek miestų yra Jungtinėse Amerikos Valstijose

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> 

>

>

Išvestis 

true>

Laiko sudėtingumas: O(sqrt(n))
Pagalbinė erdvė: O(1)

Veiksmingi sprendimai

  • Pirmumo testas | 1 rinkinys (įvadas ir mokyklos metodas)
  • Pirmumo testas | 2 rinkinys (Fermato metodas)
  • Pirmumo testas | 3 rinkinys (Mileris – Rabinas)
  • Pirmumo testas | 4 rinkinys (Solovay-Strassen)
  • Luko pirmumo testas

Algoritmai, skirti rasti visus pirminius skaičius, mažesnius už N.

  • Eratosteno sietelis
  • Eratosteno sietelis 0(n) laiko sudėtingumu
  • Segmentinis sietas
  • Sundaramo sietelis
  • Bitwise sietas
  • Naujausi straipsniai apie sietą!

Daugiau problemų, susijusių su pirminiu numeriu

  • Raskite du skirtingus pirminius skaičius su a duotas produktas
  • Atspausdinkite visus pirminius skaičius, mažesnius arba lygius N
  • Pirminio skaičiaus rekursinė programa
  • Raskite du pirminius skaičius su a duota suma
  • Raskite didžiausią pirminių skaičių skaitmenį diapazone
  • Pirminis faktorizavimas naudojant Sieve O(log n) kelioms užklausoms
  • Programa spausdinti visus pirminius tam tikro skaičiaus veiksnius
  • Mažiausias pirminis skaičių koeficientas iki n
  • Masyvo elementų LCM pirminiai veiksniai – techcodeview.com
  • Programa Goldbacho spėjimui
  • Pirminiai skaičiai ir Fibonačis
  • Sudėtinis skaičius
  • Naujausi straipsniai apie pirminius skaičius!