Здравствуйте, дорогие читатели! Можете ли Вы сразу определить, является ли число 101 – простым? Или быстро перечислить все простые числа, меньше 102? Если да, то Вы почти наверняка пользуетесь алгоритмом, который сформулировал греческий математик Эратосфен еще до нашей эры. Если вдруг, Вы используете другой способ, то поделитесь им в комментариях.
Удивительно, но этот алгоритм популярен до сих пор. И сегодня, мы разберемся, как пользоваться тем, что называется решетом Эратосфена.
Занимательно, что поисковик так и норовит подсунуть портрет Евклида, вместо портрета Эратосфена. Хотя, про Евклида и его алгоритм, я уже написала две статьи. Ну, раз великий интернет настаивает, то в конце этой публикации прикреплю ссылку на статью про алгоритм Евклида. Там можно полюбоваться его портретом
Вы находитесь на канале Trifler, где я разбираю интересные математические задачи, а также рассуждаю на некоторые околоматематические темы. Если Вы искренне увлечены математикой, но еще не подписаны на этот канал, то самое время это исправить и вступить в наши ряды! Подписаться
Решето Эратосфена
Название, на самом деле, говорящее. Эратосфен, действительно, отбирал простые числа при помощи своеобразного решета.
Конечно, постоянные читатели моего канала знают, что такое простые числа. Но, возможно эта статья попадется на глаза кому-то менее информированному, поэтому напомню:
Натуральное число, большее единицы, называют простым, если оно имеет всего два натуральных делителя: единицу и само это число
Чтобы выделять простые числа, не превосходящие число n, Эратосфен предложил такой алгоритм:
При таком подходе, те числа, которые останутся не вычеркнутыми и будут являться простыми.
На самом деле, им можно пользоваться и для выделения простых чисел из какого-то отрезка натурального ряда, начинающегося не с единицы.
Ну что ж, посмотрим это на примере и вместе ответим на вопросы, которые я задала Вам в начале статьи.
Пример
Задание на картинке:
Выполняем первый шаг алгоритма: записываем все числа от 2 до 102 в порядке возрастания. Можно записывать и вместе с единицей, но нужно помнить, что она не является простым числом.
Вычеркиваем все четные числа, кроме двойки, так как они кратны двум:
Вычеркиваем числа, кратные трем, кроме тройки:
Давайте выясним, до каких пор этот процесс будет продолжаться:
Получается, что вычеркивание будет продолжаться до тех пор, пока мы не вычеркнем числа кратные 10. Далее, я подробно не буду описывать каждый шаг. Суть уже ясна. И, не забываем зачеркнуть единицу.
При чем, задача упрощается, так как, например, числа кратные четырем, шести, восьми и десяти уже вычеркнуты. Ведь они также кратны и двум. По сути, остается вычеркнуть только те числа, которые кратны простым числам, находящимся в промежутке от 4 до 10.
Таким образом, те числа, которые остались не вычеркнутыми и будут являться простыми. Давайте выпишем их:
Вот мы и получили ответ.
Если Вам понравилась статья, то обязательно ставьте лайки и комментируйте ее. Это поспособствует тому, чтобы ее увидело много людей!
Ссылка на статью про алгоритм Евклида, в которой можно полюбоваться его портретом:
Как Евклид находил наибольший общий делитель. Простейший способ
Эта страница содержит список первых 500 простых чисел (от 2 до 3571), а также списки некоторых специальных типов простых чисел.
Первые простые числа[править | править код]
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 | 151 | 157 | 163 | 167 | 173 |
179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |
283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 |
419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 | 541 |
547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 | 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 | 659 |
661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 | 733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 | 809 |
811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 | 863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 | 941 |
947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 | 1009 | 1013 | 1019 | 1021 | 1031 | 1033 | 1039 | 1049 | 1051 | 1061 | 1063 | 1069 |
1087 | 1091 | 1093 | 1097 | 1103 | 1109 | 1117 | 1123 | 1129 | 1151 | 1153 | 1163 | 1171 | 1181 | 1187 | 1193 | 1201 | 1213 | 1217 | 1223 |
1229 | 1231 | 1237 | 1249 | 1259 | 1277 | 1279 | 1283 | 1289 | 1291 | 1297 | 1301 | 1303 | 1307 | 1319 | 1321 | 1327 | 1361 | 1367 | 1373 |
1381 | 1399 | 1409 | 1423 | 1427 | 1429 | 1433 | 1439 | 1447 | 1451 | 1453 | 1459 | 1471 | 1481 | 1483 | 1487 | 1489 | 1493 | 1499 | 1511 |
1523 | 1531 | 1543 | 1549 | 1553 | 1559 | 1567 | 1571 | 1579 | 1583 | 1597 | 1601 | 1607 | 1609 | 1613 | 1619 | 1621 | 1627 | 1637 | 1657 |
1663 | 1667 | 1669 | 1693 | 1697 | 1699 | 1709 | 1721 | 1723 | 1733 | 1741 | 1747 | 1753 | 1759 | 1777 | 1783 | 1787 | 1789 | 1801 | 1811 |
1823 | 1831 | 1847 | 1861 | 1867 | 1871 | 1873 | 1877 | 1879 | 1889 | 1901 | 1907 | 1913 | 1931 | 1933 | 1949 | 1951 | 1973 | 1979 | 1987 |
1993 | 1997 | 1999 | 2003 | 2011 | 2017 | 2027 | 2029 | 2039 | 2053 | 2063 | 2069 | 2081 | 2083 | 2087 | 2089 | 2099 | 2111 | 2113 | 2129 |
2131 | 2137 | 2141 | 2143 | 2153 | 2161 | 2179 | 2203 | 2207 | 2213 | 2221 | 2237 | 2239 | 2243 | 2251 | 2267 | 2269 | 2273 | 2281 | 2287 |
2293 | 2297 | 2309 | 2311 | 2333 | 2339 | 2341 | 2347 | 2351 | 2357 | 2371 | 2377 | 2381 | 2383 | 2389 | 2393 | 2399 | 2411 | 2417 | 2423 |
2437 | 2441 | 2447 | 2459 | 2467 | 2473 | 2477 | 2503 | 2521 | 2531 | 2539 | 2543 | 2549 | 2551 | 2557 | 2579 | 2591 | 2593 | 2609 | 2617 |
2621 | 2633 | 2647 | 2657 | 2659 | 2663 | 2671 | 2677 | 2683 | 2687 | 2689 | 2693 | 2699 | 2707 | 2711 | 2713 | 2719 | 2729 | 2731 | 2741 |
2749 | 2753 | 2767 | 2777 | 2789 | 2791 | 2797 | 2801 | 2803 | 2819 | 2833 | 2837 | 2843 | 2851 | 2857 | 2861 | 2879 | 2887 | 2897 | 2903 |
2909 | 2917 | 2927 | 2939 | 2953 | 2957 | 2963 | 2969 | 2971 | 2999 | 3001 | 3011 | 3019 | 3023 | 3037 | 3041 | 3049 | 3061 | 3067 | 3079 |
3083 | 3089 | 3109 | 3119 | 3121 | 3137 | 3163 | 3167 | 3169 | 3181 | 3187 | 3191 | 3203 | 3209 | 3217 | 3221 | 3229 | 3251 | 3253 | 3257 |
3259 | 3271 | 3299 | 3301 | 3307 | 3313 | 3319 | 3323 | 3329 | 3331 | 3343 | 3347 | 3359 | 3361 | 3371 | 3373 | 3389 | 3391 | 3407 | 3413 |
3433 | 3449 | 3457 | 3461 | 3463 | 3467 | 3469 | 3491 | 3499 | 3511 | 3517 | 3527 | 3529 | 3533 | 3539 | 3541 | 3547 | 3557 | 3559 | 3571 |
(последовательность A000040 в OEIS).
Проект по проверке проблемы Гольдбаха сообщает, что были вычислены все простые числа до . Это составляет 24 739 954 287 740 860 простых чисел, но они не были сохранены. Существуют известные формулы, позволяющие вычислить количество простых чисел (до заданного значения) быстрее, чем вычисление самих простых чисел. Этот способ был использован, чтобы вычислить, что до находится 1 925 320 391 606 803 968 923 простых числа.
Простые числа Белла[править | править код]
Простые числа, которые являются числом разбиения множества с элементами.
2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837. Следующее число имеет 6539 цифр[1]. (последовательность A051131 в OEIS)
Кубические простые числа[править | править код]
Простые числа вида
7, 19, 37, 61, 127, 271, 331, 397, 547, 631, 919, 1657, 1801, 1951, 2269, 2437, 2791, 3169, 3571, 4219, 4447, 5167, 5419, 6211, 7057, 7351, 8269, 9241, 10267, 11719, 12097, 13267, 13669, 16651, 19441, 19927, 22447, 23497, 24571, 25117, 26227, 27361, 33391, 35317 (последовательность A002407 в OEIS).
а также
13, 109, 193, 433, 769, 1201, 1453, 2029, 3469, 3889, 4801, 10093, 12289, 13873, 18253, 20173, 21169, 22189, 28813, 37633, 43201, 47629, 60493, 63949, 65713, 69313, 73009, 76801, 84673, 106033, 108301, 112909, 115249
(последовательность A002648 в OEIS).
Суперпростые числа[править | править код]
Простые числа, находящиеся на позициях последовательности простых чисел с простыми номерами, то есть 2-е, 3-е, 5-е и т. д.
Первые члены последовательности суперпростых чисел: 3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, …
Последовательность OEIS:A006450
Простые, состоящие из единиц[править | править код]
Числа-репьюниты, состоящие из 19, 23, 317, 1031, 49081, 86453, 109297, 270343 единиц, являются простыми (последовательность A004023 в OEIS).
Простые, состоящие из единиц и нулей[править | править код]
Кроме простых чисел, состоящих только из единиц, можно отметить и простые числа, состоящие из единиц и нулей. В пределах первых десяти миллионов простыми являются следующие из таких чисел (последовательность A020449 в OEIS):
11, 101, 10111, 101111, 1011001, 1100101 и т. д.
Простые палиндромы[править | править код]
Палиндромами называются числа, которые справа налево и слева направо читаются одинаковым образом, например, 30103.
Среди таких чисел тоже встречаются простые. Ясно, что любой простой палиндром состоит из нечётного количества цифр (за исключением числа 11), так как любой палиндром с чётным количеством цифр всегда делится на 11.
Первыми простыми палиндромами являются такие числа:
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601
Простые числа Вильсона[править | править код]
Простые числа , для которых делится нацело на .
Известные простые Вильсона: 5, 13, 563 (последовательность A007540 в OEIS).
Другие простые Вильсона неизвестны. Гарантированно не существует других простых Вильсона, меньших 2⋅1013[2].
Простые числа Вольстенхольма[править | править код]
Простые числа , для которых биномиальный коэффициент .
Известны только эти числа до миллиарда: 16843, 2124679 (последовательность A088164 в OEIS)
Простые числа Кэрола[править | править код]
Простые числа вида .
7, 47, 223, 3967, 16127, 1046527, 16769023, 1073676287, 68718952447, 274876858367, 4398042316799, 1125899839733759, 18014398241046527, 1298074214633706835075030044377087 (последовательность A091516 в OEIS).
Простые числа Каллена[править | править код]
Простые числа вида .
Все известные числа Каллена соответствуют , равному:
- 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881 последовательность A005849 в OEIS.
Есть предположение, что имеется бесконечно много простых чисел Каллена.
Простые числа Маркова[править | править код]
Простые числа , для которых существуют целые и такие, что .
2, 5, 13, 29, 89, 233, 433, 1597, 2897, 5741, 7561, 28657, 33461, 43261, 96557, 426389, 514229 (последовательность A178444 в OEIS)
Простые числа Мерсенна[править | править код]
Простые числа вида . Первые 12 чисел:
3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727
(последовательность A000668 в OEIS).
Простые числа Ньюмена — Шэнкса — Уильямса[править | править код]
Простым числом Ньюмена — Шэнкса — Уильямса (NSW) называется простое число , которое можно записать в виде:
Несколько первых NSW-простых: 7, 41, 239, 9369319, 63018038201, 489133282872437279, 19175002942688032928599, 123426017006182806728593424683999798008235734137469123231828679 (последовательность A088165 в OEIS).
Простые числа Прота[править | править код]
Простые числа вида , причём нечётно и (последовательность A080076 в OEIS).
Простые числа Софи Жермен[править | править код]
Простые числа такие, что также простые.
2, 3, 5, 7, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953
(последовательность A005384 в OEIS).
Простые числа Ферма[править | править код]
Это простые числа вида .
Известные простые числа Ферма: 3, 5, 17, 257, 65537 (последовательность A019434 в OEIS).
Простые числа Фибоначчи[править | править код]
Простые числа в последовательности Фибоначчи F0 = 0, F1 = 1,
Fn = Fn−1 + Fn−2.
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917 (последовательность A005478 в OEIS)
Простые числа Чена[править | править код]
Такие простые числа , что либо простое, либо полупростое:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89, 101, 107, 109, 113, 127, 131, 137, 139, 149, 157, 167, 179, 181, 191, 197, 199, 211, 227, 233, 239, 251, 257, 263, 269, 281, 293, 307, 311, 317, 337, 347, 353, 359, 379, 389, 401, 409 (последовательность A109611 в OEIS).
Простые числа Пелля[править | править код]
В теории чисел числами Пелля называется бесконечная последовательность целых чисел, являющихся знаменателями подходящих дробей для квадратного корня из 2. Эта последовательность приближений начинается с 1/1, 3/2, 7/5, 17/12, и 41/29, так что последовательность чисел Пелля начинается с 1, 2, 5, 12 и 29. Несколько первых простых чисел Пелля: 2, 5, 29, 5741, … (последовательность A086383 в OEIS).
Простые числа в форме [править | править код]
[3][4]
2, 17, 257, 1297, 65537, 160001, 331777, 614657, 1336337, 4477457, 5308417, 8503057, 9834497, 29986577, 40960001, 45212177, 59969537, 65610001, 126247697, 193877777, 303595777, 384160001, 406586897, 562448657, 655360001 (последовательность A037896 в OEIS).
Сбалансированные простые числа[править | править код]
Простые числа, которые являются средним арифметическим предыдущего простого числа и следующего простого числа:
5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, 1103, 1123, 1187, 1223, 1367, 1511, 1747, 1753, 1907, 2287, 2417, 2677, 2903, 2963, 3307, 3313, 3637, 3733, 4013, 4409, 4457, 4597, 4657, 4691, 4993, 5107, 5113, 5303, 5387, 5393 (последовательность A006562 в OEIS).
Уникальные простые числа[править | править код]
Простые числа , длина периодической дроби которых от уникальна (ни одно другое простое число не даёт такое же):
3, 11, 37, 101, 9091, 9901, 333667, 909091, 99990001, 999999000001, 9999999900000001, 909090909090909091, 1111111111111111111, 11111111111111111111111, 900900900900990990990991
(последовательность A040017 в OEIS).
Факториальные простые[править | править код]
Это простые числа вида для некоторого :
2, 3, 5, 7, 23, 719, 5039, 39916801, 479001599, 87178291199, 10888869450418352160768000001, 265252859812191058636308479999999, 263130836933693530167218012159999999, 8683317618811886495518194401279999999 (последовательность A088054 в OEIS).
Праймориальные простые числа[править | править код]
Простые числа вида p# ± 1:
- pn# − 1 является простым для n = 2, 3, 5, 6, 13, 24, … последовательность A057704 в OEIS
- pn# + 1 является простым для n = 1, 2, 3, 4, 5, 11, … последовательность A014545 в OEIS
Центрированные квадратные простые числа[править | править код]
Числа вида :
5, 13, 41, 61, 113, 181, 313, 421, 613, 761, 1013, 1201, 1301, 1741, 1861, 2113, 2381, 2521, 3121, 3613, 4513, 5101, 7321, 8581, 9661, 9941, 10513, 12641, 13613, 14281, 14621, 15313, 16381, 19013, 19801, 20201, 21013, 21841, 23981, 24421, 26681 (последовательность A027862 в OEIS).
Центрированные треугольные простые числа[править | править код]
Числа вида :
19, 31, 109, 199, 409, 571, 631, 829, 1489, 1999, 2341, 2971, 3529, 4621, 4789, 7039, 7669, 8779, 9721, 10459, 10711, 13681, 14851, 16069, 16381, 17659, 20011, 20359, 23251, 25939, 27541, 29191, 29611, 31321, 34429, 36739, 40099, 40591, 42589 (последовательность A125602 в OEIS).
Центрированные десятиугольные простые числа[править | править код]
Простые числа, которые можно представить в виде :
11, 31, 61, 101, 151, 211, 281, 661, 911, 1051, 1201, 1361, 1531, 1901, 2311, 2531, 3001, 3251, 3511, 4651, 5281, 6301, 6661, 7411, 9461, 9901, 12251, 13781, 14851, 15401, 18301, 18911, 19531, 20161, 22111, 24151, 24851, 25561, 27011, 27751 (последовательность A090562 в OEIS).
Примечания[править | править код]
- ↑ 93074010508593618333…(6499 other digits)…83885253703080601131 Архивная копия от 6 февраля 2015 на Wayback Machine, The Largest Known Primes — primes.utm.edu
- ↑ A Search for Wilson primes. Дата обращения: 20 декабря 2012. Архивировано 7 апреля 2018 года.
- ↑ Lal, M. Primes of the Form n4 + 1 (англ.) // Mathematics of Computation (англ.) (рус. : journal. — American Mathematical Society, 1967. — Vol. 21. — P. 245—247. — ISSN 1088-6842. — doi:10.1090/S0025-5718-1967-0222007-9. Архивировано 13 января 2015 года.
- ↑ Bohman, J. New primes of the form n4 + 1 (англ.) // BIT Numerical Mathematics (англ.) (рус. : journal. — Springer, 1973. — Vol. 13, no. 3. — P. 370—372. — ISSN 1572-9125. — doi:10.1007/BF01951947.
Литература[править | править код]
- Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4.
Ссылки[править | править код]
- Списки простых и факторизованных составных чисел
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1.
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Составное число – это натуральное число, имеющее более двух положительных делителей.
Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а, то есть оно будет делиться само на себя и на 1. Дадим определение целых чисел.
Натуральные числа, которые не являются простыми, называют составными.
Простые числа: 2, 3, 11, 17, 131, 523. Они делятся только сами на себя и на 1. Составные числа: 6, 63, 121, 6697. То есть число 6 можно разложить на 2 и 3, а 63 на 1, 3, 7,9, 21, 63, а 121 на 11, 11, то есть его делители будут 1, 11, 121. Число 6697 разложится на 37 и 181. Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.
Таблица простых чисел
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000, тогда следует задуматься об использовании решета Эратосфена.
Рассмотрим теорему, которая объясняет последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Возьмем, что а является натуральным числом, которое больше 1, b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.
Допустим, что b – составное число. Отсюда имеем, что есть делитель для b, который отличен от 1 как и от b. Такой делитель обозначается как b1. Необходимо, чтобы условие 1<b1<b было выполнено.
Из условия видно, что а делится на b, b делится на b1, значит, понятие делимости выражается таким образом: a=b·q и b=b1·q1, откуда a= b1·(q1·q), где q и q1 являются целыми числами. По правилу умножения целых чисел имеем, что произведение целых чисел – целое число с равенством вида a=b1·(q1·q). Видно, что b1 – это делитель для числа а. Неравенство 1<b1<b не соответствует, потому как получим, что b является наименьшим положительным и отличным от 1 делителем а.
Простых чисел бесконечно много.
Предположительно возьмем конечное количество натуральных чисел n и обозначим как p1, p2, …, pn. Рассмотрим вариант нахождения простого числа, отличного от указанных.
Примем на рассмотрение число р, которое равняется p1, p2, …, pn+1. Оно не равняется каждому из чисел, соответствующих простым числам вида p1, p2, …, pn. Число р является простым. Тогда считается, что теорема доказана. Если оно составное, тогда нужно принять обозначение pn+1 и показать несовпадение делителя ни с одним из p1, p2, …, pn.
Если это было бы не так, тогда, исходя из свойства делимости произведения p1, p2, …, pn, получим, что оно делилось бы на pn+1. Заметим, что на выражение pn+1 делится число р равняется сумме p1, p2, …, pn+1. Получим, что на выражение pn+1 должно делиться второе слагаемое этой суммы, которое равняется 1, но это невозможно.
Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.
Так как простых чисел очень много, то таблицы ограничивают числами 100, 1000, 10000 и так далее.
Решето Эратосфена
При составлении таблицы простых чисел следует учитывать то, что для такой задачи необходима последовательная проверка чисел, начиная с 2 до 100. При отсутствии делителя оно фиксируется в таблицу, если оно составное, то в таблицу не заносится.
Рассмотрим пошагово.
Если начать с числа 2, то оно имеет только 2 делителя: 2 и 1, значит, его можно занести в таблицу. Также и с числом 3. Число 4 является составным, следует разложить его еще на 2 и 2. Число 5 является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа 100.
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа 2, 3, 4, …, 50.
Теперь необходимо зачеркнуть все числа, которые кратны 2. Произвести последовательное зачеркивание. Получим таблицу вида:
Далее вычеркиваем все числа, кратные 3. Получаем таблицу вида:
Переходим к вычеркиванию чисел, кратных 5. Получим:
Вычеркиваем числа, кратные 7, 11. В конечном итоге таблица получает вид
Перейдем к формулировке теоремы.
Наименьший положительный и отличный от 1 делитель основного числа а не превосходит a, где a является арифметическим корнем заданного числа.
Необходимо обозначить b наименьший делитель составного числа а. Существует такое целое число q, где a=b·q, причем имеем, что b≤q. Недопустимо неравенство вида b>q, так как происходит нарушение условия. Обе части неравенства b≤q следует умножить на любое положительное число b, не равное 1. Получаем, что b·b≤b·q, где b2≤a и b≤a.
Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа , которое равняется b2 и удовлетворяет неравенству b2≤a. То есть, если вычеркнуть числа, кратные 2, то процесс начинается с 4, а кратных 3 – с 9 и так далее до 100.
Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n. В примере, где n=50, у нас имеется, что n=50. Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50. Поиск чисел производится при помощи вычеркивания.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Доказать что число 898989898989898989 является составным.
Решение
Сумма цифр заданного числа равняется 9·8+9·9=9·17. Значит, число 9·17 делится на 9, исходя из признака делимости на 9. Отсюда следует, что оно составное.
Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a. То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.
Определить составное или простое число 11723.
Решение
Теперь необходимо найти все делители для числа 11723. Необходимо оценить 11723.
Отсюда видим, что 11723<200, то 2002=40 000, а 11 723<40 000. Получаем, что делители для 11 723 меньше числа 200.
Для более точной оценки числа 11723 необходимо записать выражение 1082=11 664, а 1092=11 881, то 1082<11 723<1092. Отсюда следует, что 11723<109. Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
При разложении получим, что 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 – это все простые числа. Весь данный процесс можно изобразить как деление столбиком. То есть разделить 11723 на 19. Число 19 является одним из его множителей, так как получим деление без остатка. Изобразим деление столбиком:
Отсюда следует, что 11723 является составным числом, потому как кроме себя и 1 имеет делитель 19.
Ответ: 11723 является составным числом.
Содержание материала
- Что такое простые числа
- Видео
- Разложение на простые множители
- Алгоритм разложения на простые множители
- Решение
- Разные свойства простых чисел*
- Метод Марена Мерсенна
- Быстрое возведение в степень
- Скатерть Улама
- Решето Эратосфена
- Как определить простые числа
- Темы для размышлений
Что такое простые числа
Простые числа — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.
Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом.
13 ÷ 4 = 3 (остаток 1).
Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.
30 не является примером простого числа, потому что его можно разделить на 1,2,3,5,6,10,15,30. Таким образом, 30 является примером составного числа, поскольку оно имеет более двух факторов.
Ноль, единица и числа меньше единицы не считаются простыми числами.
Видео
Разложение на простые множители
Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.
[11 = 11 = 11^1] [100 = 2 times 2 times 5 times 5 = 2^2 times 5^2] [126 = 2 times 3 times 3 times 7 = 2^1 times 3^2 times 7^1]
Рассмотрим, например, такую задачу:
Условие: Нужно разбить (N) людей на группы равного размера. Нам интересно, какие размеры это могут быть.
Решение: По сути нас просят найти число делителей (N). Нужно посмотреть на разложение числа (N) на простые множители, в общем виде оно выглядит так:
[N= p_1^{a_1} times p_2^{a_2} times ldots times p_k^{a_k}]
Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень (i)-го простого число от 0 до (a_i) (то есть (a_i+1) различное значение), и так для каждого. То есть делитель (N) выглядит ровно так: [M= p_1^{b_1} times p_2^{b_2} times ldots times p_k^{b_k}, 0 leq b_i leq a_i] Значит, ответом будет произведение ((a_1+1) times (a_2+1) times ldots times (a_k + 1)).
Алгоритм разложения на простые множители
Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа (N), мы можем число (N) на него поделить и продолжить искать новый минимальный простой делитель.
Будем перебирать простой делитель от (2) до корня из (N) (как и раньше), но в случае, если (N) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ((N) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда (N) стало либо (1), либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само (N) добавить в ответ.
Напишем алгоритм факторизации:
Решение
За те же самые (O(sqrt{N})). Итераций цикла while с перебором делителя будет не больше, чем (sqrt{N}). Причем ровно (sqrt{N}) операций будет только в том случае, если (N) — простое.
А итераций деления (N) на делители будет столько, сколько всего простых чисел в факторизации числа (N). Понятно, что это не больше, чем (O(log{N})).
Разные свойства простых чисел*
Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:
- Простых чисел, меньших (N), примерно (frac{N}{ln N}).
- N-ое простое число равно примерно (Nln N).
- Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
- Для любого (N ge 2) на интервале ((N, 2N)) всегда найдется простое число (Постулат Бертрана)
- Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с (N! + 2).
- Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
- Максимальное число делителей равно примерно (O(sqrt[3]{n})). Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
- Максимальное число делителей у числа на отрезке ([1, 10^5]) — 128
- Максимальное число делителей у числа на отрекзке ([1, 10^9]) — 1344
- Максимальное число делителей у числа на отрезке ([1, 10^{18}]) — 103680
- Наука умеет факторизовать числа за (O(sqrt[4]{n})), но об этом как-нибудь в другой раз.
- Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.
Метод Марена Мерсенна
Метод простого числа Мерсенна — это специальный метод нахождения определенного вида простого числа, известный как простые числа Мерсенна. Название для этого метода происходит от французского монаха Марин Мерсенн, который первым определил его. Простые числа Мерсенна — это те, которые сводимы к виду 2n-1, где n-простое число. Первые несколько чисел в этом методе являются 2, 3, 5, 7, 13, 17, 19, 31, 61, и 89. Долгое время метод простых чисел Мерсенна представлял собой тяжёлую работу, так как при переходе к более высоким простым числам он был очень трудоемким.
Однако, с появлением компьютеров, они теперь могли выполнять эти вычислительные вычисления, которые раньше делались людьми самым кропотливым и трудоемким образом. Мы определенно достигли более высоких простых чисел Мерсенна и простых чисел на общем уровне. Поиск простых чисел так же активен, как и другие численные поиски, выполняемые компьютерами. Другой числовой поиск, аналогичный движению простых чисел, заключается в добавлении десятичных разрядов к некоторым иррациональным числам, таким как пи (отношение длины окружности к диаметру). Однако непрерывный поиск следующего по величине простого числа существенно сложнее, чем поиск следующей цифры числа Пи.
Даже самые большие компьютеры (суперкомпьютеры) тратят значительное количество времени, чтобы проверить, является ли новое число (которое обычно ошеломляюще огромным) само по себе простым числом, и требуется еще больше времени, чтобы проверить, является ли число основным числом Мерсенна. По этой причине числа Мерсенна представляют большой интерес в области кибербезопасности и криптографии, особенно в отношении шифрования.
В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!
Быстрое возведение в степень
Задача: > Даны натуральные числа (a, b, c < 10^9). Найдите (a^b) (mod (c)).
Мы хотим научиться возводить число в большую степень быстро, не просто умножая (a) на себя (b) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.
Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):
- (3^2)
- (3^4)
- (3^8)
- (3^{16})
- (3^{32})
- (3^{33})
- (3^{66})
- (3^{132})
- (3^{133})
- (3^{266})
- (3^{532})
- (3^{533})
- (3^{1066})
Да, здесь специально приведена такая последовательность, в которой каждое следующее число легко считается через предыдущее: его либо нужно умножить на (a=3), либо возвести в квадрат. Так и получается рекурсивный алгоритм:
- (a^0 = 1)
- (a^{2k}=(a^{k})^2)
- (a^{2k+1}=a^{2k}times a)
Нужно только после каждой операции делать mod: * (a^0 pmod c = 1) * (a^{2k} pmod c = (a^{k} pmod c)^2 pmod c) * (a^{2k+1} pmod c = ((a^{2k}pmod c) times a) pmod c)
Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)
Асимптотика этого алгоритма, очевидно, (O(log c)) — за каждые две итерации число уменьшается хотя бы в 2 раза.
Скатерть Улама
Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.
Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.
Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный многочлен x задаёт бесконечно много простых чисел, более того, все простые числа, но это неинтересный случай. А что можно сказать о многочлене ax+b (где a, b и x — натуральные числа)? Ясно, что если a и b имеют общий делитель, отличный от 1, то значение многочлена ax+b — число составное, кратное этому делителю. Случай же, когда a и b взаимно просты, гораздо менее очевиден.
Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что если a и b взаимно просты, то в арифметической прогрессии с первым членом b и разностью a встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в XIX столетии немецким математиком Леженом Дирихле.
Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен x2 + x + 41 — его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при x = 1, 2, …, 40. При x = 41 его значение — составное.
Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.
Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама 5. Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль какой-либо диагонали в пределах, ограниченных на рис. 1 красными линиями — это значения некоторого квадратного многочлена с целыми коэффициентами).
197 | 196 | 195 | 194 | 193 | 192 | 191 | 190 | 189 | 188 | 187 | 186 | 185 | 184 | 183 |
198 | 145 | 144 | 143 | 142 | 141 | 140 | 139 | 138 | 137 | 136 | 135 | 134 | 133 | 182 |
199 | 146 | 101 | 100 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 132 | 181 |
200 | 147 | 102 | 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 | 90 | 131 | 180 |
201 | 148 | 103 | 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 | 89 | 130 | 179 |
202 | 149 | 104 | 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 | 88 | 129 | 178 |
203 | 150 | 105 | 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 | 87 | 128 | 177 |
204 | 151 | 106 | 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 | 86 | 127 | 176 |
205 | 152 | 107 | 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 | 85 | 126 | 175 |
206 | 153 | 108 | 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 | 84 | 125 | 174 |
207 | 154 | 109 | 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 83 | 124 | 173 |
208 | 155 | 110 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 123 | 172 |
209 | 156 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 171 |
210 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 |
211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
Рис. 1.
Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел — на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название «скатерть Улама».
Рис. 2.
Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена x2 + x + 41 выстраиваются по диагоналям у спирали, начинающейся с числа 41 (рис. 3).
57 | 56 | 55 | 54 | 53 |
58 | 45 | 44 | 43 | 52 |
59 | 46 | 41 | 42 | 51 |
60 | 47 | 48 | 49 | 50 |
61 | 62 | 63 | 64 | 65 |
Рис. 3.
Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.
Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил какого-либо математического объяснения.
О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
- Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
- Вычеркнуть все числа, которые делятся на 2 (кроме 2);
- Вычеркнуть все числа, которые делятся на 3 (кроме 3);
- И так далее по порядку со всеми невычеркнутыми числами до числа n (после 3 это 5, 7, 11, 13, 17 и т. д.).
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Как определить простые числа
Сначала попробуйте разделить его на 2 и посмотреть, получится ли целое число. Если да, то оно не может быть простым числом. Если вы не получите целое число, затем попробуйте разделить его на простые числа: 3, 5, 7, 11 (9 делится на 3) и так далее, всегда делясь на простое число.
8 простых чисел до 20: 2, 3, 5, 7, 11, 13, 17 и 19.
Первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Таблица простых чисел до 1000:
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 | 151 | 157 | 163 | 167 |
173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 |
229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |
281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 |
349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 |
409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 |
463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |
541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 |
601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 |
659 | 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |
733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 |
809 | 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |
863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 |
941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
2 — наименьшее простое число. Это также единственное четное простое число — все остальные четные числа могут быть разделены сами по себе на 1 и 2, что означает, что у них будет, по крайней мере, 3 фактора.
Один из самых известных математиков классической эпохи, Евклид, записал доказательство того, что не существует самого большого простого числа. Самое большое известное простое число (по состоянию на ноябрь 2020 года) составляет 282 589 933-1, число, которое имеет 24 862 048 цифр при записи в базе 10. До этого самым большим известным простым числом было 277 232 917-1, состоящее из 23 249 425 цифр.
За исключением 2 и 3, все остальные простые числа могут быть выражены в общей форме как 6n + 1 или 6n — 1, где n — натуральное число.
Чтобы определить, является ли число простым или составным, нужно решить пример на делимость в следующем порядке (от простого к сложному): 2, 5, 3, 11, 7, и 13. Если вы обнаружите, что число делится на одно из них, и вы знаете, что оно составное, не нужно выполнять остальные тесты.
Если число меньше 121 не делится на 2, 3, 5 или 7, оно простое; в противном случае оно составное.
Если число меньше 289 не делится на 2, 3, 5, 7, 11, или 13, это простое число; в противном случае оно составное.
Темы для размышлений
1. |
Докажите, что в арифметических прогрессиях 3, 7, 11, … и 5, 11, 17, … бесконечно много простых чисел. |
2. |
Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль (см. рис. 1) • начата с 1? • начата с некоторого числа u? • начата с некоторого числа u, и по спирали стоят члены арифметической прогрессии u, u + v, u + 2v, …? |
3. |
Теорема Вильсона утверждает, что если p — простое число, то (p–1)! + 1 делится на p. Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальном многочлене R, задающем простые числа? |
4. |
Постройте экспоненциальный многочлен S(x, …, xk ), который задаёт множество полусумм простых чисел-близнецов, т.е. такой многочлен, что если S(x, …, xk ) > 0, то оба числа S(x, …, xk ) – 1 и S(x, …, xk ) + 1 являются простыми, и наоборот, если s – 1 и s + 1 — простые числа, то S(x, …, xk ) = s при некоторых x, …, xk . |
5. |
Постройте экспоненциальный многочлен T(q, x, …, xm ), такой, что • если q — простое число, то существуют числа x, …, xm такие, что T(q, x, …, xm ) > 0; • если q — простое число и T(q, x, …, xm ) > 0, то T(q, x, …, xm ) — простое число, следующее за q; • если q не является простым числом, то всегда T(q, x, …, xm ) ≤ 0. Этот экспоненциальный многочлен даёт «формулу для следующего простого числа». |
Теги
Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23… Единица не является ни простым числом, ни составным.
Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).
Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).
Все натуральные числа считаются либо простыми, либо составными (кроме 1).
Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4… (нет ни дробей, ни 0, ни чисел ниже 0).
Зачастую множество простых чисел в математике обозначается буквой P.
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 |
151 |
157 |
163 |
167 |
173 |
179 |
181 |
191 |
193 |
197 |
199 |
211 |
223 |
227 |
229 |
233 |
239 |
241 |
251 |
257 |
263 |
269 |
271 |
277 |
281 |
283 |
293 |
307 |
311 |
313 |
317 |
331 |
337 |
347 |
349 |
353 |
359 |
367 |
373 |
379 |
383 |
389 |
397 |
401 |
409 |
419 |
421 |
431 |
433 |
439 |
443 |
449 |
457 |
461 |
463 |
467 |
479 |
487 |
491 |
499 |
503 |
509 |
521 |
523 |
541 |
547 |
557 |
563 |
569 |
571 |
577 |
587 |
593 |
599 |
601 |
607 |
613 |
617 |
619 |
631 |
641 |
643 |
647 |
653 |
659 |
661 |
673 |
677 |
683 |
691 |
701 |
709 |
719 |
727 |
733 |
739 |
743 |
751 |
757 |
761 |
769 |
773 |
787 |
797 |
809 |
811 |
821 |
823 |
827 |
829 |
839 |
853 |
857 |
859 |
863 |
877 |
881 |
883 |
887 |
907 |
911 |
919 |
929 |
937 |
941 |
947 |
953 |
967 |
971 |
977 |
983 |
991 | 997 |
Как определить, является ли число простым?
Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.
Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).
Более структурированный метод — это решето Эратосфена.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
- Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
- Вычеркнуть все числа, которые делятся на 2 (кроме 2);
- Вычеркнуть все числа, которые делятся на 3 (кроме 3);
- И так далее по порядку со всеми невычеркнутыми числами до числа n (после 3 это 5, 7, 11, 13, 17 и т. д.).
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Взаимно простые числа
Это натуральные числа, у которых 1 — это единственный общий делитель. Например:
- 14 (это 2 х 7) и 15 (это 3 х 5), единственный общий делитель — 1; если числа следуют одно за другим (как 13 и 12 либо 10 и 11), то они всегда будут взаимно простыми;
- 7 (это 7 х 1) и 11 (это 11 х 1) — это два простых числа, а значит единственный общий делитель всегда будет только единица, простые числа всегда являются взаимно простыми;
- или 30 и 48 не являются взаимно простыми, т. к. 6 х 5 = 30 и 6 х 8 = 48 и 6 — это наибольший общий делитель, т. е.: НОД (30; 48) = 6.
Число Мерсенна
Простое число Мерсенна — это простое число вида:
До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).
Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.
Почему 1 не является простым числом?
Российские математики Боревич и Шафаревич в своей знаменитой работе “Теория чисел” (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.
Почему 4 не является простым числом?
Простое число — это натуральное число, больше единицы, которое делится без остатка на 1 и на само себя. Т. к. 4 можно разделить на 1, на 2 и на 4, из-за деления на 2 оно не является простым.
Самое большое простое число
21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:
Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).
Узнайте про Рациональные числа и Натуральные числа.