logo

TechCodeview

Pirmskaitļi

Kas ir pirmskaitļi?

A pirmskaitlis ir definēts kā naturāls skaitlis, kas ir lielāks par 1 un dalās tikai ar 1 un sevi.

Citiem vārdiem sakot, pirmskaitlis ir pozitīvs vesels skaitlis, kas ir lielāks par 1 un kuram ir tieši divi faktori — 1 un pats skaitlis. Pirmie pirmskaitļi ir 2, 3, 5, 7, 11, 13, 17, 19, 23. . .



Piezīme: 1 nav ne galvenais, ne salikts. Pārējie skaitļi, izņemot 1, tiek klasificēti kā pirmskaitļi un saliktie skaitļi.

pirmskaitļi

Daži interesanti fakti par primārajiem skaitļiem:

  • Izņemot 2, kas ir mazākais pirmskaitlis un vienīgais pāra pirmskaitlis, visi pirmskaitļi ir nepāra skaitļi.
  • Katru pirmskaitli var attēlot formā 6n + 1 vai 6n – 1 izņemot pirmskaitļus 2 un 3 , kur n ir jebkurš naturāls skaitlis.
  • 2. un 3 ir tikai divi secīgi naturāli skaitļi, kas ir pirmskaitļi.
  • Goldbaha minējums: Katru pāra veselu skaitli, kas ir lielāks par 2, var izteikt kā divu pirmskaitļu summu.
  • Vilsona teorēma : Vilsona teorēma nosaka, ka naturāls skaitlis p> 1 ir pirmskaitlis tad un tikai tad

(p – 1) ! ≡ -1 pret p
VAI,
(p – 1) ! ≡ (p-1) mod p



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

  • Pirmskaitļa teorēma : Varbūtība, ka dots, nejauši izvēlēts skaitlis n ir galvenais, ir apgriezti proporcionāls tā ciparu skaitam vai n logaritmam.
  • Lemuāna minējums : Jebkuru nepāra veselu skaitli, kas ir lielāks par 5, var izteikt kā nepāra pirmskaitļa (visi pirmskaitļi, izņemot 2, ir nepāra) un pāra pusskaitļa summu. Daļskaitlis ir divu pirmskaitļu reizinājums. To sauc par Lemuāna minējumu.

Pirmskaitļu īpašības:

  • Katru skaitli, kas ir lielāks par 1, var dalīt ar vismaz vienu pirmskaitli.
  • Katru pat pozitīvu veselu skaitli, kas ir lielāks par 2, var izteikt kā divu pirmskaitļu summu.
  • Izņemot 2, visi pārējie pirmskaitļi ir nepāra. Citiem vārdiem sakot, mēs varam teikt, ka 2 ir vienīgais pāra pirmais skaitlis.
  • Divi pirmskaitļi vienmēr ir viens otra pirmskaitļi.
  • Katru salikto skaitli var ieskaitīt primārajos faktoros, un atsevišķi tie visi ir unikāli pēc būtības.

Pirmskaitļi un pirmskaitļi:

Ir svarīgi atšķirt pirmskaitļi un līdzcilvēki . Tālāk ir norādītas atšķirības starp pirmskaitļiem un blakusskaitļiem.

  • Pirmskaitļi vienmēr tiek uzskatīti par pāri, turpretim pirmskaitlis ir viens skaitlis.
  • Koppirmā skaitļi ir skaitļi, kuriem nav kopēja faktora, izņemot 1. Turpretim pirmskaitļiem šāda nosacījuma nav.
  • Koppirmskaitlis var būt pirmskaitlis vai salikts, taču tā lielākajam kopējam faktoram (GCF) vienmēr jābūt 1. Atšķirībā no saliktajiem skaitļiem pirmskaitļiem ir tikai divi faktori — 1 un pats skaitlis.
  • Līdzfinansējuma piemērs: 13 un 15 ir pirmskaitļi. Koeficienti 13 ir 1 un 13 un koeficienti 15 ir 1, 3 un 5. Var redzēt, ka tiem ir tikai 1 kā kopīgs faktors, tāpēc tie ir kopskaitļi.
  • Primera piemērs: Daži pirmskaitļu piemēri ir 2, 3, 5, 7 un 11 utt.

Kā pārbaudīt, vai skaitlis ir galvenais vai nē?

Naiva pieeja: Naiva pieeja ir



Atkārtojiet no 2 līdz (n-1) un pārbaudiet, vai kāds skaitlis šajā diapazonā dalās n . Ja skaitlis dalās n , tad tas nav pirmskaitlis.

Laika sarežģītība: O(N)
Palīgtelpa: O(1)

Naiva pieeja (rekursīva): Rekursiju var izmantot arī, lai pārbaudītu, vai skaitlis starp 2 uz n – 1 dala n. Ja atrodam kādu skaitli, kas dala, mēs atgriežam false.

Tālāk ir sniegta iepriekš minētās idejas īstenošana:

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

j e s t 

>

>

Izvade 

 false>

Laika sarežģītība: O(N)
Palīgtelpa: O(N), ja ņemam vērā rekursijas steku. Pretējā gadījumā tas ir O(1).

Efektīva pieeja: Efektīvs risinājums ir:

Atkārtojiet visus skaitļus no 2 kvadrātsaknei no n un katram skaitlim pārbaudiet, vai tas dala n [jo ja skaitlis ir izteikts kā n = xy un jebkurš no x vai y ir lielāks par n sakni, otram jābūt mazākam par saknes vērtību]. Ja atrodam kādu skaitli, kas dala, mēs atgriežam false.

Tālāk ir norādīta ieviešana:

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

alfabēts uz cipariem




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

Laika sarežģītība: O(sqrt(n))
Palīgtelpa: O(1)

Vēl viena efektīva pieeja: Lai pārbaudītu, vai skaitlis ir pirmais vai nē, izpildiet tālāk sniegto ideju:

Mēs aplūkosim dažus skaitļus, piemēram, 1, 2, 3, un skaitļus, kas dalās ar 2 un 3 atsevišķos gadījumos un atlikušajiem skaitļiem. Atkārtojiet no 5 līdz sqrt(n) un katrai iterācijai pārbaudiet, vai (šī vērtība) vai (šī vērtība + 2) dala n vai ne, un palieliniet vērtību ar 6 [jo jebkuru pirmskaitļu var izteikt kā 6n+1 vai 6n-1 ]. Ja atrodam kādu skaitli, kas dala, mēs atgriežam false.

Tālāk ir sniegta iepriekš minētās idejas īstenošana:

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

polimorfisms java




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

>

>

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> 

>

>

Izvade 

true>

Laika sarežģītība: O(sqrt(n))
Palīgtelpa: O(1)

Efektīvi risinājumi

  • Primitātes tests | 1. komplekts (ievads un skolas metode)
  • Primitātes tests | 2. komplekts (Fermata metode)
  • Primitātes tests | 3. komplekts (Millers–Rabins)
  • Primitātes tests | 4. seta (Solovay-Strassen)
  • Lūkasa primāruma tests

Algoritmi, lai atrastu visus pirmskaitļus, kas ir mazāki par N.

  • Eratostena siets
  • Eratostēna siets 0(n) laika sarežģītībā
  • Segmentēts siets
  • Sundarama siets
  • Bitu siets
  • Jaunākie raksti par sietu!

Vairāk problēmu, kas saistītas ar galveno numuru

  • Atrodiet divus atšķirīgus pirmskaitļus ar a dotais produkts
  • Drukājiet visus pirmskaitļus, kas ir mazāki vai vienādi ar N
  • Rekursīva programma pirmskaitļam
  • Atrodiet divus pirmskaitļus ar a dotā summa
  • Atrodiet augstāko ciparu, kas sastopams pirmajā diapazonā
  • Galvenā faktorizēšana, izmantojot Sieve O(log n) vairākiem vaicājumiem
  • Programma visu dotā skaitļa galveno faktoru drukāšanai
  • Mazākais skaitļu pirmfaktors līdz n
  • Masīva elementu LCM pirmfaktori – techcodeview.com
  • Programma Goldbaha minējumiem
  • Pirmskaitļi un Fibonači
  • Salikts numurs
  • Jaunākie raksti par pirmskaitļiem!