LICZBY PIERWSZE - TECHCODEVIEW.COM

Co to są liczby pierwsze?

A Liczba pierwsza definiuje się jako liczbę naturalną większą niż 1 i jest podzielna tylko przez 1 i samą siebie.

Innymi słowy, liczba pierwsza to dodatnia liczba całkowita większa od 1, która ma dokładnie dwa dzielniki: 1 i samą liczbę. Kilka pierwszych liczb pierwszych to 2, 3, 5, 7, 11, 13, 17, 19, 23. . .

Notatka: 1 nie jest ani liczbą pierwszą, ani złożoną. Pozostałe liczby, z wyjątkiem 1, zaliczamy do liczb pierwszych i złożonych.

liczby pierwsze

Kilka interesujących faktów na temat liczb pierwszych:

Z wyjątkiem 2, który jest najmniejszy Liczba pierwsza i jedyną parzystą liczbą pierwszą, wszystkie liczby pierwsze są liczbami nieparzystymi.
Każdą liczbę pierwszą można przedstawić w postaci 6n + 1 Lub 6n – 1 z wyjątkiem liczb pierwszych 2 I 3 , gdzie n jest dowolną liczbą naturalną.
2 i 3 to tylko dwie kolejne liczby naturalne, które są pierwsze.
Hipoteza Goldbacha: Każdą liczbę parzystą większą niż 2 można wyrazić jako sumę dwóch liczb pierwszych.
Twierdzenie Wilsona : Twierdzenie Wilsona stwierdza, że liczba naturalna p> 1 jest liczbą pierwszą wtedy i tylko wtedy

(p – 1) ! ≡ -1 przeciwko p
LUB,
(p – 1) ! ≡ (p-1) mod p

Małe twierdzenie Fermata : Jeśli n jest liczbą pierwszą, to dla każdego a 1 ≤ a

A^n-1≡ 1 (mod n)
LUB,
A^n-1% n = 1

Twierdzenie o liczbach pierwszych : Prawdopodobieństwo, że dana, losowo wybrana liczba n jest liczbą pierwszą, jest odwrotnie proporcjonalne do liczby jej cyfr lub do logarytmu n.
Hipoteza Lemoine’a : Każdą nieparzystą liczbę całkowitą większą niż 5 można wyrazić jako sumę nieparzystej liczby pierwszej (wszystkie liczby pierwsze inne niż 2 są nieparzyste) i parzystej liczby półpierwszej. Liczba półpierwsza jest iloczynem dwóch liczb pierwszych. Nazywa się to hipotezą Lemoine’a.

Właściwości liczb pierwszych:

Każdą liczbę większą od 1 można podzielić przez co najmniej jedną liczbę pierwszą.
Każdą parzystą dodatnią liczbę całkowitą większą niż 2 można wyrazić jako sumę dwóch liczb pierwszych.
Z wyjątkiem 2, wszystkie inne liczby pierwsze są nieparzyste. Innymi słowy, możemy powiedzieć, że 2 jest jedyną parzystą liczbą pierwszą.
Dwie liczby pierwsze są zawsze względnie pierwsze.
Każdą liczbę złożoną można rozłożyć na czynniki pierwsze i każdy z nich ma indywidualny charakter.

Liczby pierwsze i liczby współpierwsze:

Ważne jest, aby rozróżnić liczby pierwsze I liczby współpierwsze . Poniżej przedstawiono różnice między liczbami pierwszymi i współpierwszymi.

Liczby względnie pierwsze są zawsze traktowane jako para, podczas gdy liczba pierwsza jest liczbą pojedynczą.
Liczby współpierwsze to liczby, które nie mają wspólnego dzielnika z wyjątkiem 1. Natomiast liczby pierwsze nie mają takiego warunku.
Liczba współpierwsza może być liczbą pierwszą lub złożoną, ale jej największy wspólny dzielnik (GCF) musi zawsze wynosić 1. W przeciwieństwie do liczb złożonych, liczby pierwsze mają tylko dwa dzielniki: 1 i samą liczbę.
Przykład współ-prime: 13 a 15 to liczby współpierwsze. Dzielniki liczby 13 to 1 i 13, a czynniki liczby 15 to 1, 3 i 5. Widzimy, że mają one tylko 1 jako wspólny dzielnik, zatem są to liczby względnie pierwsze.
Przykład liczby pierwszej: Kilka przykładów liczb pierwszych to 2, 3, 5, 7 i 11 itd.

Jak sprawdzić, czy liczba jest liczbą pierwszą, czy nie?

Naiwne podejście: Naiwne podejście polega na tym, że

Iteruj od 2 do (n-1) i sprawdź, czy jakakolwiek liczba z tego zakresu dzieli się N . Jeśli liczba się dzieli N , to nie jest to liczba pierwsza.

Złożoność czasowa: NA)
Przestrzeń pomocnicza: O(1)

Podejście naiwne (rekurencyjne): Rekurencji można również użyć do sprawdzenia, czy liczba z zakresu 2 do n – 1 dzieli n. Jeśli znajdziemy liczbę, która dzieli, zwracamy wartość false.

Poniżej realizacja powyższego pomysłu:

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>

Jawa

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

Neena Gupta

Wyjście

 false>

Złożoność czasowa: NA)
Przestrzeń pomocnicza: O(N), jeśli weźmiemy pod uwagę stos rekurencji. W przeciwnym razie jest to O(1).

Efektywne podejście: Skutecznym rozwiązaniem jest:

Iteruj po wszystkich liczbach z 2 do pierwiastka kwadratowego z N i dla każdej liczby sprawdź, czy dzieli n [ponieważ jeśli liczba jest wyrażona jako n = xy i którekolwiek z x lub y jest większe od pierwiastka z n, drugie musi być mniejsze od wartości pierwiastkowej]. Jeśli znajdziemy liczbę, która dzieli, zwracamy wartość false.

Poniżej implementacja:

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;> }>

Jawa

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

lista tablic w Javie

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

Wyjście

true>

Złożoność czasowa: O(kwadrat(n))
Przestrzeń pomocnicza: O(1)

Inne skuteczne podejście: Aby sprawdzić, czy liczba jest pierwsza, postępuj zgodnie z poniższym pomysłem:

Zajmiemy się kilkoma liczbami, takimi jak 1, 2, 3 oraz liczbami podzielnymi przez 2 i 3 w oddzielnych przypadkach i dla pozostałych liczb. Iteruj od 5 do sqrt(n) i sprawdzaj przy każdej iteracji, czy (ta wartość) lub (ta wartość + 2) dzieli n, czy nie, i zwiększ wartość o 6 [ponieważ dowolną liczbę pierwszą można wyrazić jako 6n+1 lub 6n-1 ] Jeśli znajdziemy liczbę, która dzieli, zwracamy wartość false.

Poniżej implementacja powyższego pomysłu:

C++

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

Jawa

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

szary kod

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

Wyjście

true>

Złożoność czasowa: O(kwadrat(n))
Przestrzeń pomocnicza: O(1)

Wydajne rozwiązania

Test pierwszości | Zestaw 1 (wprowadzenie i metoda szkolna)
Test pierwszości | Zestaw 2 (metoda Fermata)
Test pierwszości | Zestaw 3 (Miller – Rabin)
Test pierwszości | Zestaw 4 (Solovay-Strassen)
Test pierwszości Lucasa

Algorytmy znajdowania wszystkich liczb pierwszych mniejszych od N.

Sito Eratostenesa
Sito Eratostenesa w złożoności czasowej 0(n).
Segmentowe sito
Sito Sundarama
Sito bitowe
Najnowsze artykuły na temat Sive!

Więcej problemów związanych z liczbą pierwszą

Znajdź dwie różne liczby pierwsze za pomocą A dany produkt
Wypisz wszystkie liczby pierwsze mniejsze lub równe N
Program rekurencyjny dla liczby pierwszej
Znajdź dwie liczby pierwsze za pomocą A podana suma
Znajdź najwyższą cyfrę występującą w liczbach pierwszych w zakresie
Faktoryzacja pierwsza przy użyciu sita O(log n) dla wielu zapytań
Program wypisujący wszystkie czynniki pierwsze danej liczby
Najmniejszy czynnik pierwszy liczb do n
Czynniki pierwsze LCM elementów tablicy – techcodeview.com
Program hipotezy Goldbacha
Liczby pierwsze i Fibonacciego
Liczba złożona
Najnowsze artykuły na temat liczb pierwszych!