www.wikidata.uk-ua.nina.az

Просте число це натуральне число яке має рівно два різні натуральні дільники лише 1 і саме число Решту чисел окрім одини

Просте число

Просте число  — це натуральне число, яке має рівно два різні натуральні дільники (лише 1 і саме число). Решту чисел, окрім одиниці, називають складеними. Таким чином, всі натуральні числа, більші від одиниці, розбивають на прості і складені. Теорія чисел вивчає властивості простих чисел. В теорії кілець простим числам відповідають незвідні елементи.

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

Послідовність простих чисел починається так:

Розклад натуральних чисел на добуток простих

Основна теорема арифметики стверджує, що кожне натуральне число більше одиниці (1), можна представити як добуток простих чисел, причому, в єдиний спосіб з точністю до порядку множників. Таким чином, прості числа — це елементарні «будівельні блоки» натуральних чисел.

Представлення натурального числа у вигляді добутку простих називають розкладом на прості або факторизацією числа. Тепер невідомі Поліноміальні алгоритми факторизації чисел, хоча і не доведено, що таких алгоритмів не існує (тут і далі мова йде про поліноміальною залежності часу роботи алгоритму від логарифма розміру числа, тобто від кількості його цифр). На припущенні про високу обчислювальну складність задачі факторизації базується криптосистема RSA.

Тести простоти

Ератосфен Киренський.

Решето Ератосфена, решето Сундарама та решето Аткіна дають прості способи складання початкового списку простих чисел до певного значення.

Однак на практиці замість отримання списку простих чисел найчастіше потрібно перевірити, чи є дане число простим. Алгоритми, які вирішують це завдання, називають тестами простоти. Існує безліч поліноміальних тестів простоти, але більшість з них є стохастичними (наприклад, тест Міллера — Рабина) і використовуються для потреб криптографії. Тільки в 2002 році було доведено, що завдання перевірки на простоту в загальному вигляді можна розв'язати за поліноміальний час, але запропонований детермінований алгоритм має досить велику складність, що ускладнює його застосування на практиці.

Для деяких класів чисел існують спеціалізовані ефективні тести простоти. Наприклад, для перевірки на простоту чисел Мерсенна використовують тест Люка — Лемера, а для перевірки на простоту чисел Ферма — тест Пепіно.

Скільки існує простих чисел?

Простих чисел нескінченно багато. Найдавніше відоме доведення цього факту дав Евклід у «Началах» (книга IX, твердження 20). Його доведення може бути коротко відтворено так:

Математики пропонували інші докази. Одне з них (наведене Ейлером) показує, що сума всіх чисел, обернених до простих є розбіжною.

Відома теорема про розподіл простих чисел стверджує, що кількість простих чисел менших за n, яке позначають як , зростає як , тобто

Найбільше відоме просте число

Здавна ведуться записи, в яких відзначають найбільші відомі на той час прості числа. Один з рекордів поставив свого часу Ейлер, знайшовши просте число .

Найбільшим відомим простим числом станом на червень 2009 року є . Воно складається з 12 978 189 десяткових цифр і є простим числом Мерсенна (M43112609). Його знайшли 23 серпня 2008 року на математичному факультеті університету UCLA в рамках проекту по розподіленому пошуку простих чисел Мерсенна GIMPS. Попереднє за величиною відоме просте, також є простим числом Мерсенна M37156667, було знайдено 6 вересня 2007 року учасником проекту GIMPS Гансом-Міхаелем Елвеніхом (нім. Hans-Michael Elvenich).

7 січня 2016 був поставлений новий рекорд: проект GIMPS знайшов ще більше просте число: , що складається з 22 338 618 десяткових цифр. Нове просте число також є простим числом Мерсенна — M74207281. Нове просте число було обчислене множенням 74 207 281 двійок та відніманням 1. Перевірка простоти тривала 31 добу безперервних обчислень на комп'ютері з процесором Intel I7-4790. Результати перевірки були незалежно підтверджені іншими розробниками з використанням іншого апаратного та програмного забезпечення.

Числа Мерсенна вигідно відрізняються від решти наявністю ефективного тесту простоти: тесту Люка — Лемера. Завдяки йому прості числа Мерсенна давно утримують рекорд як найбільші відомі прості.

За знаходження простих чисел з понад 100 000 000 та 1 000 000 000 десяткових цифр EFF призначила грошові призи в 150 000 та 250 000 доларів США відповідно.

Деякі властивості

Відкриті питання

Досі існує багато відкритих запитань щодо простих чисел, найвідоміші з яких були перераховані Едмундом Ландау на П'ятому Міжнародному математичному конгресі :

  1. Проблема Гольдбаха (перша проблема Ландау): довести або спростувати, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел.
  2. Друга проблема Ландау : чи нескінченна множина «простих близнюків» — простих чисел, різниця між якими дорівнює 2?
  3. Гіпотеза Лежандра (третя проблема Ландау) чи правильно, що між і завжди знайдеться просте число?
  4. Четверта проблема Ландау: чи нескінченна множина простих чисел виду ?

Відкритою проблемою є також існування нескінченної кількості простих чисел у багатьох цілочисельних послідовностях, включаючи числа Фібоначчі, числа Ферма і т. д.

Застосування

Великі прості числа (порядку ) використовують в криптографії з відкритим ключем. Прості числа також використовують в хеш-таблицях і для генерації псевдовипадкових чисел (зокрема, в генераторі псевдовипадкових чисел Вихор Мерсенна).


Програма обчислення простих чисел на C++

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (Квітень 2020) 
#include <iostream>  bool is_prime(int const num)  {    if (num <= 3)    {        return num > 1;    }    else if (num % 2 == 0 || num % 3 == 0)    {        return false;    }    else    {        for (int i = 5; i * i <= num; i += 6)        {          if (num % i == 0 || num % (i + 2) == 0)          {              return false;          }        }        return true;    }  }


Варіації і узагальнення

Історія

Математичний Папірус Рінда

Математичний Папірус Рінда, що має вік близько від 1550 р.до.н.е, описує різні форми розкладання єгипетських дробів для простих і складених чисел. Однак, самим раннім відомим записом про явне дослідження простих чисел відноситься до математики Стародавньої Греції. Евклід у своїй роботі Елементи (близько 300 р.до.н.е.) довів нескінченність простих чисел[en] і основну теорему арифметики, і показав як побудувати досконале число із Числа Мерсенна.

Число один

Більшість філософів стародавньої Греції навіть не розглядали 1 як число, тому вони навіть не розглядали чи є воно простим. Декілька математиків тих часів вважали, що прості числа є підмножиною непарних чисел, тому вони також не розглядали випадок що число 2 може бути простим. Однак, Евклід і більшість інших Грецьких математиків розглядали 2 як просте число. Ісламські математики середньовіччя здебільшого наслідували Греків і також не розглядали число 1 як число. У середні віки і в часи Ренесансу математики почали ставитися до 1 як до числа, і деякі з них відносили його до першого простого числа. У середині 18-го століття Християн Гольдбах перелічив число 1 як просте у своєму листуванні з Леонардом Ейлером; однак сам Ейлер не розглядав 1 як просте. В 19-му столітті багато математиків досі продовжували вважати число 1 простим, а переліки простих чисел, в яких включали 1 продовжували публікувати до 1956 р.

Якби визначення простих чисел було змінене, так щоб до них віднести одиницю, багато тверджень, які стосуються простих чисел необхідно було б переформулювати у досить не зручний спосіб. Наприклад, основну теорему арифметики необхідно було б перефразувати так щоб розкладання виконувалося у прості множники що більші за 1, оскільки кожне число мало б множину способів розкладання із різною кількістю повторених 1. Аналогічно, не правильно б працювало Решето Ератосфена якби число 1 вважалося простим, оскільки в ньому усі числа є кратними 1 і результатом було б лише одне число 1. Деякі інші властивості простих чисел також не виконуються для випадку з 1: наприклад, формули для Функції Ейлера або для суми функції дільників відрізняються для простих чисел і для 1. До початку 20-го століття, математики дійшли згоди, що число 1 не повинне належати до простих чисел, а скоріше належить до своєї власної окремої категорії "одиниці".

Див. також

Примітки

  1. Weisstein, Eric W. AKS Primality Test(англ.) на сайті Wolfram MathWorld.
  2. . Архів оригіналу за 5 червня 2020. Процитовано 23 березня 2010. 
  3. Great Internet Mersenne Prime Search (GIMPS). Архів оригіналу за 11 листопада 2021. Процитовано 20 січня 2016. 
  4. EFF Cooperative Computing Awards [ 4 червня 2004 у Wayback Machine.] (англ.)
  5. Jones JP, Sato D., Wada H., Wiens D (1976). . Amer. Math. Mon. 83 (6): 449–464. Архів оригіналу за 31 березня 2010. Процитовано 23 березня 2010. 
  6. Yuri Matiyasevich, Diophantine Equations in the XX Century[недоступне посилання з квітня 2019]
  7. Matijasevic's polynomial [ 6 серпня 2010 у Wayback Machine.]. The Prime Glossary.
  8. Weisstein, Eric W. Landau's Problems(англ.) на сайті Wolfram MathWorld.
  9. Bruins, Evert Marie, review in Mathematical Reviews of Gillings, R. J. (1974). The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it?. Archive for History of Exact Sciences 12: 291–298. MR 0497458. doi:10.1007/BF01307175. 
  10. Stillwell, John (2010). . Undergraduate Texts in Mathematics (вид. 3rd). Springer. с. 40. ISBN 9781441960528. Архів оригіналу за 27 липня 2021. Процитовано 3 квітня 2018. 
  11. ↑ Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). . Journal of Integer Sequences 15 (9): Article 12.9.8. MR 3005523. Архів оригіналу за 12 квітня 2018. Процитовано 3 квітня 2018.  For a selection of quotes from and about the ancient Greek positions on this issue, see in particular pp. 3–4. For the Islamic mathematicians, see p. 6.
  12. Tarán, Leonardo (1981). . Philosophia Antiqua : A Series of Monographs on Ancient Philosophy 39. BRILL. с. 35–38. ISBN 9789004065055. Архів оригіналу за 23 березня 2019. Процитовано 3 квітня 2018. 
  13. (Caldwell та ін., 2012), pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.
  14. (Caldwell та ін., 2012), p. 15.
  15. ↑ Caldwell, Chris K.; Xiong, Yeng (2012). . Journal of Integer Sequences 15 (9): Article 12.9.7. MR 3005530. Архів оригіналу за 12 квітня 2018. Процитовано 3 квітня 2018. 
  16. Riesel, Hans (1994). (вид. 2nd). Basel, Switzerland: Birkhäuser. с. 36. ISBN 978-0-8176-3743-9. MR 1292250. Архів оригіналу за 23 березня 2019. Процитовано 3 квітня 2018. 
  17. ↑ Conway, John Horton; Guy, Richard K. (1996). The Book of Numbers. New York: Copernicus. с. 129–130. ISBN 978-0-387-97993-9. MR 1411676. 
  18. For the totient, see (Sierpiński, 1988), p. 245 [ 23 березня 2019 у Wayback Machine.]. For the sum of divisors, see Sandifer, C. Edward (2007). . MAA Spectrum. Mathematical Association of America. с. 59. ISBN 9780883855638. Архів оригіналу за 23 березня 2019. Процитовано 3 квітня 2018. 

Література

  • Трост Эрнст. Простые числа / Перевод с немецкого. — Москва: Государственное издательство физико-математической литературы, 1959. — 136 с.
  • Мир математики: В 40 томах. — Т. 3: Энрике Грасиан. Простые числа. Долгая дорога к бесконечности / Перевод с аглийского. — Москва: Де Агостини, 2014. — 144 с.

Посилання

Вікіпідручник має книгу на тему
Основні числові системи
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Proste chislo ce naturalne chislo yake maye rivno dva rizni naturalni dilniki lishe 1 i same chislo Reshtu chisel okrim odinici nazivayut skladenimi Takim chinom vsi naturalni chisla bilshi vid odinici rozbivayut na prosti i skladeni Teoriya chisel vivchaye vlastivosti prostih chisel V teoriyi kilec prostim chislam vidpovidayut nezvidni elementi Naturalni chisla vid nulya do sta Prosti chisla poznacheno chervonim kolorom Poslidovnist prostih chisel pochinayetsya tak 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 poslidovnist A000040 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Zmist 1 Rozklad naturalnih chisel na dobutok prostih 2 Testi prostoti 3 Skilki isnuye prostih chisel 4 Najbilshe vidome proste chislo 5 Deyaki vlastivosti 6 Vidkriti pitannya 7 Zastosuvannya 8 Programa obchislennya prostih chisel na C 9 Variaciyi i uzagalnennya 10 Istoriya 10 1 Chislo odin 11 Div takozh 12 Primitki 13 Literatura 14 PosilannyaRozklad naturalnih chisel na dobutok prostih RedaguvatiDokladnishe Faktorizaciya ta Prostij mnozhnikOsnovna teorema arifmetiki stverdzhuye sho kozhne naturalne chislo bilshe odinici 1 mozhna predstaviti yak dobutok prostih chisel prichomu v yedinij sposib z tochnistyu do poryadku mnozhnikiv Takim chinom prosti chisla ce elementarni budivelni bloki naturalnih chisel Predstavlennya naturalnogo chisla u viglyadi dobutku prostih nazivayut rozkladom na prosti abo faktorizaciyeyu chisla Teper nevidomi Polinomialni algoritmi faktorizaciyi chisel hocha i ne dovedeno sho takih algoritmiv ne isnuye tut i dali mova jde pro polinomialnoyu zalezhnosti chasu roboti algoritmu vid logarifma rozmiru chisla tobto vid kilkosti jogo cifr Na pripushenni pro visoku obchislyuvalnu skladnist zadachi faktorizaciyi bazuyetsya kriptosistema RSA Testi prostoti RedaguvatiDokladnishe Test prostoti Eratosfen Kirenskij Resheto Eratosfena resheto Sundarama ta resheto Atkina dayut prosti sposobi skladannya pochatkovogo spisku prostih chisel do pevnogo znachennya Odnak na praktici zamist otrimannya spisku prostih chisel najchastishe potribno pereviriti chi ye dane chislo prostim Algoritmi yaki virishuyut ce zavdannya nazivayut testami prostoti Isnuye bezlich polinomialnih testiv prostoti ale bilshist z nih ye stohastichnimi napriklad test Millera Rabina i vikoristovuyutsya dlya potreb kriptografiyi Tilki v 2002 roci bulo dovedeno 1 sho zavdannya perevirki na prostotu v zagalnomu viglyadi mozhna rozv yazati za polinomialnij chas ale zaproponovanij determinovanij algoritm maye dosit veliku skladnist sho uskladnyuye jogo zastosuvannya na praktici Dlya deyakih klasiv chisel isnuyut specializovani efektivni testi prostoti Napriklad dlya perevirki na prostotu chisel Mersenna vikoristovuyut test Lyuka Lemera a dlya perevirki na prostotu chisel Ferma test Pepino Skilki isnuye prostih chisel RedaguvatiProstih chisel neskinchenno bagato Najdavnishe vidome dovedennya cogo faktu dav Evklid u Nachalah kniga IX tverdzhennya 20 Jogo dovedennya mozhe buti korotko vidtvoreno tak Uyavimo sho kilkist prostih chisel skinchenna Peremnozhimo yih i dodamo odinicyu Otrimane chislo ne dilitsya na zhodne zi skinchennogo naboru prostih chisel tomu sho zalishok vid dilennya na bud yake z nih daye odinicyu Znachit dobutok maye dilitis na deyake proste chislo ne vklyuchene do cogo naboru Matematiki proponuvali inshi dokazi Odne z nih navedene Ejlerom pokazuye sho suma vsih chisel obernenih do prostih ye rozbizhnoyu Vidoma teorema pro rozpodil prostih chisel stverdzhuye sho kilkist prostih chisel menshih za n yake poznachayut yak p n displaystyle pi n zrostaye yak n ln n displaystyle n ln n tobtop n n ln n 1 n displaystyle frac pi n n ln n to 1 quad n to infty Najbilshe vidome proste chislo RedaguvatiDokladnishe Najbilshe vidome proste chisloZdavna vedutsya zapisi v yakih vidznachayut najbilshi vidomi na toj chas prosti chisla 2 Odin z rekordiv postaviv svogo chasu Ejler znajshovshi proste chislo 2 31 1 2147483647 displaystyle 2 31 1 2147483647 Najbilshim vidomim prostim chislom stanom na cherven 2009 roku ye 2 43112609 1 displaystyle 2 43112609 1 Vono skladayetsya z 12 978 189 desyatkovih cifr i ye prostim chislom Mersenna M43112609 Jogo znajshli 23 serpnya 2008 roku na matematichnomu fakulteti universitetu UCLA v ramkah proektu po rozpodilenomu poshuku prostih chisel Mersenna GIMPS Poperednye za velichinoyu vidome proste takozh ye prostim chislom Mersenna M37156667 bulo znajdeno 6 veresnya 2007 roku uchasnikom proektu GIMPS Gansom Mihaelem Elvenihom nim Hans Michael Elvenich 7 sichnya 2016 buv postavlenij novij rekord proekt GIMPS znajshov she bilshe proste chislo 2 74207281 1 displaystyle 2 74207281 1 sho skladayetsya z 22 338 618 desyatkovih cifr Nove proste chislo takozh ye prostim chislom Mersenna M74207281 Nove proste chislo bulo obchislene mnozhennyam 74 207 281 dvijok ta vidnimannyam 1 Perevirka prostoti trivala 31 dobu bezperervnih obchislen na komp yuteri z procesorom Intel I7 4790 Rezultati perevirki buli nezalezhno pidtverdzheni inshimi rozrobnikami z vikoristannyam inshogo aparatnogo ta programnogo zabezpechennya 3 Chisla Mersenna vigidno vidriznyayutsya vid reshti nayavnistyu efektivnogo testu prostoti testu Lyuka Lemera Zavdyaki jomu prosti chisla Mersenna davno utrimuyut rekord yak najbilshi vidomi prosti Za znahodzhennya prostih chisel z ponad 100 000 000 ta 1 000 000 000 desyatkovih cifr EFF priznachila 4 groshovi prizi v 150 000 ta 250 000 dolariv SShA vidpovidno Deyaki vlastivosti RedaguvatiYaksho p displaystyle p proste i p p dilit a b displaystyle ab to p p dilit a a abo b displaystyle b Cyu vlastivist doviv Evklid i vidoma vona yak lema Evklida Yiyi vikoristovuyut pri dovedenni osnovnoyi teoremi arifmetiki Kilce ostach Z n mathbb Z n ye polem todi i tilki todi koli n n proste Harakteristika kozhnogo polya nul abo proste chislo Yaksho p p proste a a naturalne to a p a displaystyle a p a dilitsya na p p mala teorema Ferma Yaksho G G skinchenna grupa z p n displaystyle p n elementiv to G G mistit element poryadku p p Yaksho G G skinchenna grupa i p n displaystyle p n maksimalnij stepin p p yakij dilit G displaystyle G to G G maye pidgrupu poryadku p n displaystyle p n yaku nazivayut pidgrupoyu Silova bilshe togo kilkist pidgrup Silova dorivnyuye p k 1 displaystyle pk 1 dlya deyakogo cilogo k k teoremi Silova Naturalne p gt 1 displaystyle p gt 1 ye prostim todi i tilki todi koli p 1 1 displaystyle p 1 1 dilitsya na p p teorema Vilsona Yaksho n gt 1 n gt 1 naturalne to isnuye proste p displaystyle p Take sho n lt p lt 2 n displaystyle n lt p lt 2n postulat Bertrana Ryad chisel obernenih do prostih ye rozbizhnim Bilshe togo pri x displaystyle x to infty p lt x 1 p ln ln x displaystyle sum p lt x frac 1 p sim ln ln x Bud yaka arifmetichna progresiya vidu a a q a 2 q a 3 q displaystyle a a q a 2q a 3q de a q gt 1 displaystyle a q gt 1 cili vzayemno prosti chisla mistit neskinchenno bagato prostih chisel Teorema Dirihle pro prosti chislah v arifmetichnij progresiyi Bud yake proste chislo bilshe 3 mozhna predstaviti u viglyadi 6 k 1 displaystyle 6k 1 abo u viglyadi 6 k 1 displaystyle 6k 1 de k k deyake naturalne chislo Yaksho p gt 3 displaystyle p gt 3 proste to p 2 1 displaystyle p 2 1 kratne 24 Mnozhina dodatnih znachen mnogochlena k 2 1 w z h j q 2 g k 2 g k 1 h j h z 2 2 n p q z e 2 displaystyle k 2 1 wz h j q 2 gk 2g k 1 h j h z 2 2n p q z e 2 16 k 1 3 k 2 n 1 2 1 f 2 2 e 3 e 2 a 1 2 1 o 2 2 a 2 1 y 2 1 x 2 2 displaystyle 16 k 1 3 k 2 n 1 2 1 f 2 2 e 3 e 2 a 1 2 1 o 2 2 a 2 1 y 2 1 x 2 2 16 r 2 y 4 a 2 1 1 u 2 2 a u 2 u 2 a 2 1 n 4 d y 2 1 x c u 2 2 n l v y 2 displaystyle 16r 2 y 4 a 2 1 1 u 2 2 a u 2 u 2 a 2 1 n 4dy 2 1 x cu 2 2 n l v y 2 a 2 1 l 2 1 m 2 2 a i k 1 l i 2 p l a n 1 b 2 a n 2 a n 2 2 n 2 m 2 displaystyle a 2 1 l 2 1 m 2 2 ai k 1 l i 2 p l a n 1 b 2an 2a n 2 2n 2 m 2 q y a p 1 s 2 a p 2 a p 2 2 p 2 x 2 z p l a p t 2 a p p 2 1 p m 2 displaystyle q y a p 1 s 2ap 2a p 2 2p 2 x 2 z pl a p t 2ap p 2 1 pm 2 pri nevid yemnih cilih znachennyah zminnih zbigayetsya z mnozhinoyu prostih chisel 5 6 7 Cej rezultat ye okremim vipadkom dovedennoyu Yuriyem Matiyasevichem diofantnosti bud yakoyi efektivno zlichennoyi mnozhini Vidkriti pitannya RedaguvatiDosi isnuye bagato vidkritih zapitan shodo prostih chisel najvidomishi z yakih buli pererahovani Edmundom Landau na P yatomu Mizhnarodnomu matematichnomu kongresi 8 Problema Goldbaha persha problema Landau dovesti abo sprostuvati sho kozhne parne chislo bilshe dvoh mozhe buti predstavleno u viglyadi sumi dvoh prostih chisel a kozhne neparne chislo bilshe 5 mozhe buti predstavleno u viglyadi sumi troh prostih chisel Druga problema Landau chi neskinchenna mnozhina prostih bliznyukiv prostih chisel riznicya mizh yakimi dorivnyuye 2 Gipoteza Lezhandra tretya problema Landau chi pravilno sho mizh n 2 displaystyle n 2 i n 1 2 displaystyle n 1 2 zavzhdi znajdetsya proste chislo Chetverta problema Landau chi neskinchenna mnozhina prostih chisel vidu n 2 1 displaystyle n 2 1 Vidkritoyu problemoyu ye takozh isnuvannya neskinchennoyi kilkosti prostih chisel u bagatoh cilochiselnih poslidovnostyah vklyuchayuchi chisla Fibonachchi chisla Ferma i t d Zastosuvannya RedaguvatiVeliki prosti chisla poryadku 10 300 displaystyle 10 300 vikoristovuyut v kriptografiyi z vidkritim klyuchem Prosti chisla takozh vikoristovuyut v hesh tablicyah i dlya generaciyi psevdovipadkovih chisel zokrema v generatori psevdovipadkovih chisel Vihor Mersenna Programa obchislennya prostih chisel na C RedaguvatiCej rozdil ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cej rozdil dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno Kviten 2020 include lt iostream gt bool is prime int const num if num lt 3 return num gt 1 else if num 2 0 num 3 0 return false else for int i 5 i i lt num i 6 if num i 0 num i 2 0 return false return true Variaciyi i uzagalnennya RedaguvatiV teoriyi kilec u rozdili abstraktnoyi algebri viznacheno ponyattya prostogo elementa ta prostogo idealu V teoriyi vuzliv isnuye ponyattya prostogo vuzla yakij u pevnomu sensi ne mozhe buti rozbitij na prostishi vuzli Istoriya Redaguvati Matematichnij Papirus RindaMatematichnij Papirus Rinda sho maye vik blizko vid 1550 r do n e opisuye rizni formi rozkladannya yegipetskih drobiv dlya prostih i skladenih chisel 9 Odnak samim rannim vidomim zapisom pro yavne doslidzhennya prostih chisel vidnositsya do matematiki Starodavnoyi Greciyi Evklid u svoyij roboti Elementi blizko 300 r do n e doviv neskinchennist prostih chisel en i osnovnu teoremu arifmetiki i pokazav yak pobuduvati doskonale chislo iz Chisla Mersenna 10 Chislo odin Redaguvati Bilshist filosofiv starodavnoyi Greciyi navit ne rozglyadali 1 yak chislo 11 12 tomu voni navit ne rozglyadali chi ye vono prostim Dekilka matematikiv tih chasiv vvazhali sho prosti chisla ye pidmnozhinoyu neparnih chisel tomu voni takozh ne rozglyadali vipadok sho chislo 2 mozhe buti prostim Odnak Evklid i bilshist inshih Greckih matematikiv rozglyadali 2 yak proste chislo Islamski matematiki serednovichchya zdebilshogo nasliduvali Grekiv i takozh ne rozglyadali chislo 1 yak chislo 11 U seredni viki i v chasi Renesansu matematiki pochali stavitisya do 1 yak do chisla i deyaki z nih vidnosili jogo do pershogo prostogo chisla 13 U seredini 18 go stolittya Hristiyan Goldbah perelichiv chislo 1 yak proste u svoyemu listuvanni z Leonardom Ejlerom odnak sam Ejler ne rozglyadav 1 yak proste 14 V 19 mu stolitti bagato matematikiv dosi prodovzhuvali vvazhati chislo 1 prostim 15 a pereliki prostih chisel v yakih vklyuchali 1 prodovzhuvali publikuvati do 1956 r 16 17 Yakbi viznachennya prostih chisel bulo zminene tak shob do nih vidnesti odinicyu bagato tverdzhen yaki stosuyutsya prostih chisel neobhidno bulo b pereformulyuvati u dosit ne zruchnij sposib Napriklad osnovnu teoremu arifmetiki neobhidno bulo b perefrazuvati tak shob rozkladannya vikonuvalosya u prosti mnozhniki sho bilshi za 1 oskilki kozhne chislo malo b mnozhinu sposobiv rozkladannya iz riznoyu kilkistyu povtorenih 1 15 Analogichno ne pravilno b pracyuvalo Resheto Eratosfena yakbi chislo 1 vvazhalosya prostim oskilki v nomu usi chisla ye kratnimi 1 i rezultatom bulo b lishe odne chislo 1 17 Deyaki inshi vlastivosti prostih chisel takozh ne vikonuyutsya dlya vipadku z 1 napriklad formuli dlya Funkciyi Ejlera abo dlya sumi funkciyi dilnikiv vidriznyayutsya dlya prostih chisel i dlya 1 18 Do pochatku 20 go stolittya matematiki dijshli zgodi sho chislo 1 ne povinne nalezhati do prostih chisel a skorishe nalezhit do svoyeyi vlasnoyi okremoyi kategoriyi odinici 15 Div takozh RedaguvatiSpisok prostih chisel Intervali mizh prostimi chislami Stala prostih chisel Konstanta Majsselya Mertensa Skladene chislo Resheto Eratosfena Prostij mnozhnik Stepin prostogo chisla Vidkriti matematichni problemi Gipoteza Andrici 7919 Prajm asteroyid nazva yakogo oznachaye proste chislo angl prime number proste chislo nazvanij na chest chisla 7919 yake ye tisyachnim prostim chislom Primitki Redaguvati Weisstein Eric W AKS Primality Test angl na sajti Wolfram MathWorld Rekordi prostih chisel po rokah Arhiv originalu za 5 chervnya 2020 Procitovano 23 bereznya 2010 GIMPS Project Discovers Largest Known Prime Number 274 207 281 1 Great Internet Mersenne Prime Search GIMPS Arhiv originalu za 11 listopada 2021 Procitovano 20 sichnya 2016 EFF Cooperative Computing Awards Arhivovano 4 chervnya 2004 u Wayback Machine angl Jones JP Sato D Wada H Wiens D 1976 Diophantine representation of the set of prime numbers Amer Math Mon 83 6 449 464 Arhiv originalu za 31 bereznya 2010 Procitovano 23 bereznya 2010 Yuri Matiyasevich Diophantine Equations in the XX Century nedostupne posilannya z kvitnya 2019 Matijasevic s polynomial Arhivovano 6 serpnya 2010 u Wayback Machine The Prime Glossary Weisstein Eric W Landau s Problems angl na sajti Wolfram MathWorld Bruins Evert Marie review in Mathematical Reviews of Gillings R J 1974 The recto of the Rhind Mathematical Papyrus How did the ancient Egyptian scribe prepare it Archive for History of Exact Sciences 12 291 298 MR 0497458 doi 10 1007 BF01307175 Stillwell John 2010 Mathematics and Its History Undergraduate Texts in Mathematics vid 3rd Springer s 40 ISBN 9781441960528 Arhiv originalu za 27 lipnya 2021 Procitovano 3 kvitnya 2018 a b Caldwell Chris K Reddick Angela Xiong Yeng Keller Wilfrid 2012 The history of the primality of one a selection of sources Journal of Integer Sequences 15 9 Article 12 9 8 MR 3005523 Arhiv originalu za 12 kvitnya 2018 Procitovano 3 kvitnya 2018 For a selection of quotes from and about the ancient Greek positions on this issue see in particular pp 3 4 For the Islamic mathematicians see p 6 Taran Leonardo 1981 Speusippus of Athens A Critical Study With a Collection of the Related Texts and Commentary Philosophia Antiqua A Series of Monographs on Ancient Philosophy 39 BRILL s 35 38 ISBN 9789004065055 Arhiv originalu za 23 bereznya 2019 Procitovano 3 kvitnya 2018 Caldwell ta in 2012 pp 7 13 See in particular the entries for Stevin Brancker Wallis and Prestet Caldwell ta in 2012 p 15 a b v Caldwell Chris K Xiong Yeng 2012 What is the smallest prime Journal of Integer Sequences 15 9 Article 12 9 7 MR 3005530 Arhiv originalu za 12 kvitnya 2018 Procitovano 3 kvitnya 2018 Riesel Hans 1994 Prime Numbers and Computer Methods for Factorization vid 2nd Basel Switzerland Birkhauser s 36 ISBN 978 0 8176 3743 9 MR 1292250 Arhiv originalu za 23 bereznya 2019 Procitovano 3 kvitnya 2018 a b Conway John Horton Guy Richard K 1996 The Book of Numbers New York Copernicus s 129 130 ISBN 978 0 387 97993 9 MR 1411676 For the totient see Sierpinski 1988 p 245 Arhivovano 23 bereznya 2019 u Wayback Machine For the sum of divisors see Sandifer C Edward 2007 How Euler Did It MAA Spectrum Mathematical Association of America s 59 ISBN 9780883855638 Arhiv originalu za 23 bereznya 2019 Procitovano 3 kvitnya 2018 Literatura RedaguvatiTrost Ernst Prostye chisla Perevod s nemeckogo Moskva Gosudarstvennoe izdatelstvo fiziko matematicheskoj literatury 1959 136 s Mir matematiki V 40 tomah T 3 Enrike Grasian Prostye chisla Dolgaya doroga k beskonechnosti Perevod s aglijskogo Moskva De Agostini 2014 144 s Posilannya RedaguvatiVikipidruchnik maye knigu na temu Osnovni chislovi sistemi Portal Matematika Onlajn utilita dlya perevirki prostih chisel Arhivovano 17 kvitnya 2010 u Wayback Machine The Prime Pages Arhivovano 27 travnya 2009 u Wayback Machine angl Baza danih najbilshih vidomih prostih chisel PrimeGrid prime lists vsi prosti chisla znajdeni v ramkah proektu PrimeGrid Geometriya prostih i doskonalih chisel Arhivovano 28 sichnya 2022 u Wayback Machine isp Prosti chisla Arhivovano 25 lyutogo 2010 u Wayback Machine Netradicijni magichni kvadrati z prostih chisel Arhivovano 29 chervnya 2010 u Wayback Machine Najmenshi magichni kvadrati z prostih chisel Arhivovano 29 chervnya 2010 u Wayback Machine Geometrical connection between natural numbers and their factors Arhivovano 24 lipnya 2013 u Wayback Machine Yu Matiyasevich Formuli dlya prostih chisel Kvant 1975 5 S 5 13 Otrimano z https uk wikipedia org w index php title Proste chislo amp oldid 39512621