ПРОСТІ ЧИСЛА - TECHCODEVIEW.COM

Що таке прості числа?

А просте число визначається як натуральне число, більше ніж 1 і ділиться лише на 1 і саму себе.

Іншими словами, просте число — це натуральне число, більше за 1, яке має рівно два множники: 1 і саме число. Кілька перших простих чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23. . .

Примітка: 1 не є ні простим, ні складеним. Решта чисел, крім 1, класифікуються як прості і складені числа.

прості числа

Деякі цікаві факти про прості числа:

За винятком 2, які є найменшими просте число і єдине парне просте число, всі прості числа є непарними.
Кожне просте число можна представити у вигляді 6n + 1 або 6n – 1 крім простих чисел 2 і 3 , де n – будь-яке натуральне число.
2 і 3 є лише два послідовні натуральні числа, які є простими.
Гіпотеза Гольдбаха: Кожне парне ціле число, більше 2, можна виразити як суму двох простих чисел.
Теорема Вільсона : Теорема Вільсона стверджує, що натуральне число p> 1 є простим числом тоді і тільки тоді, коли

(p – 1) ! ≡ -1 проти p
АБО,
(p – 1) ! ≡ (p-1) mod p

Маленька теорема Ферма : Якщо n просте число, то для кожного a 1 ≤ a

a^n-1≡ 1 (mod n)
АБО,
a^n-1% n = 1

Теорема простих чисел : Імовірність того, що дане випадково вибране число n є простим, обернено пропорційна кількості його цифр або логарифму n.
Гіпотеза Лемуана : Будь-яке непарне ціле число, більше 5, можна виразити як суму непарного простого числа (усі прості числа, крім 2, непарні) і парного напівпростого числа. Напівпросте число — це добуток двох простих чисел. Це називається гіпотезою Лемуана.

Властивості простих чисел:

Кожне число, більше 1, можна поділити принаймні на одне просте число.
Кожне парне натуральне число, більше 2, можна виразити як суму двох простих чисел.
Крім 2, усі інші прості числа непарні. Іншими словами, можна сказати, що 2 — єдине парне просте число.
Два простих числа завжди взаємно прості.
Кожне складене число можна розкласти на прості множники, і всі вони окремо є унікальними за своєю природою.

Прості числа та співпрості числа:

Важливо розрізняти прості числа і співпрості числа . Нижче наведено відмінності між простими та спільно простими числами.

Взаємно прості числа завжди розглядаються як пара, тоді як просте число є одним числом.
Взаємопрості числа — це числа, які не мають спільного множника, окрім 1. Навпаки, прості числа не мають такої умови.
Взаємопросте число може бути простим або складеним, але його найбільший спільний множник (НСД) завжди має дорівнювати 1. На відміну від складених чисел, прості числа мають лише два множники: 1 і саме число.
Приклад спільного простого числа: 13 і 15 є співпростими. Дільники числа 13 дорівнюють 1 і 13, а множники числа 15 дорівнюють 1, 3 і 5. Ми бачимо, що спільний множник у них лише 1, тому вони є взаємно простими числами.
Приклад простого: Кілька прикладів простих чисел: 2, 3, 5, 7 і 11 тощо.

Як перевірити чи є число простим чи ні?

Наївний підхід: Наївний підхід полягає в тому, щоб

Повторіть від 2 до (n-1) і перевірте, чи якесь число в цьому діапазоні ділиться п . Якщо число ділиться п , то воно не є простим числом.

Часова складність: O(N)
Допоміжний простір: О(1)

Наївний підхід (рекурсивний): Рекурсію також можна використовувати, щоб перевірити, чи число між 2 до n – 1 ділить n. Якщо ми знаходимо будь-яке число, яке ділиться, ми повертаємо false.

Нижче наведено реалізацію вищезазначеної ідеї:

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

поліморфізм

Вихід

 false>

Часова складність: O(N)
Допоміжний простір: O(N), якщо розглядати стек рекурсії. В іншому випадку це O(1).

Ефективний підхід: Ефективним рішенням є:

Переберіть усі числа з 2 до кореня квадратного з п і для кожного числа перевірте, чи воно ділить n [тому що, якщо число виражається як n = xy і будь-який з x або y є більшим за корінь з n, інший має бути меншим за значення кореня]. Якщо ми знаходимо будь-яке число, яке ділиться, ми повертаємо false.

Нижче наведено реалізацію:

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

значення xdxd

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

Часова складність: O(sqrt(n))
Допоміжні приміщення: О(1)

Ще один ефективний підхід: Щоб перевірити, чи є число простим чи ні, дотримуйтеся наведеної нижче ідеї:

Ми будемо мати справу з кількома числами, такими як 1, 2, 3, і числами, які діляться на 2 і 3 в окремих випадках і для інших чисел. Виконайте ітерацію від 5 до sqrt(n) і перевірте для кожної ітерації, чи (це значення) або (це значення + 2) ділить n чи ні, і збільште значення на 6 [оскільки будь-яке просте число можна виразити як 6n+1 або 6n-1 ]. Якщо ми знаходимо будь-яке число, яке ділиться, ми повертаємо false.

Нижче наведено реалізацію наведеної вище ідеї:

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>

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

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

Вихід

true>

Часова складність: O(sqrt(n))
Допоміжні приміщення: О(1)

Ефективні рішення

Тест на первинність | Комплект 1 (Вступ і шкільний метод)
Тест на первинність | Набір 2 (метод Ферма)
Тест на первинність | Набір 3 (Міллер–Рабін)
Тест на первинність | Комплект 4 (Solovay-Strassen)
Тест первинності Лукаса

Алгоритми пошуку всіх простих чисел, менших за N.

Решето Ератосфена
Решето Ератосфена в 0(n) часовій складності
Сегментоване сито
Сито Сундарам
Порозрядне сито
Останні статті про Sieve!

Більше проблем, пов'язаних з простим числом

Знайдіть два різних простих числа за допомогою a даний продукт
Виведіть усі прості числа, менші або рівні N
Рекурсивна програма для простого числа
Знайдіть два простих числа за допомогою a дана сума
Знайдіть старшу цифру в простих числах у діапазоні
Розкладання на множники з використанням сита O(log n) для кількох запитів
Програма для друку всіх простих множників даного числа
Найменший простий множник чисел до n
Прості множники НОК елементів масиву – techcodeview.com
Програма для гіпотези Гольдбаха
Прості числа і Фібоначчі
Складене число
Останні статті про прості числа!