Таблиця найпростіших чисел від 1 до 1000.
У статті розглядаються поняття простих та складових чисел. Даються визначення таких чисел із прикладами. Наводимо доказ того, що кількість простих чисел необмежена і зробимо запис до таблиці простих чисел за допомогою методу Ератосфена. Буде наведено докази того, чи є число простим чи складовим.
Yandex.RTB R-A-339285-1
Прості та складові числа – визначення та приклади
Прості та складові числа відносять до цілих позитивних. Вони обов'язково мають бути більше одиниці. Дільники також поділяють на прості та складові. Щоб розуміти поняття складених чисел, необхідно попередньо вивчити поняття дільників та кратних.
Визначення 1
Простими числами називають цілі числа, які більші за одиницю і мають два позитивні дільники, тобто себе і 1 .
Визначення 2
Складовими числами називають цілі числа, які більше одиниці і мають хоча б три позитивні дільники.
Одиниця не є ні простим, ні складовим числом. Вона має лише один позитивний дільник, тому відрізняється від інших позитивних чисел. Усі цілі позитивні числа називають натуральними, тобто використовувані за рахунку.
Визначення 3
Прості числа– це натуральні числа, що мають лише два позитивні дільники.
Визначення 4
Складова кількість- Це натуральне число, що має більше двох позитивних дільників.
Будь-яке число, яке більше 1 є або простим або складним. З якості ділимості маємо, що і число а завжди будуть дільниками для будь-якого числа а, тобто воно буде ділитися саме на себе і на 1 . Дамо визначення цілих чисел.
Визначення 5
Натуральні числа, які є простими, називають складовими.
Прості числа: 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 дільник натурального числа, більшого за одиницю, є простим числом.
Доказ 1
Візьмемо, що а є натуральним числом, яке більше 1 b є найменшим відмінним від одиниці дільником для числа а. Слід довести, що b є простим числом за допомогою протилежного методу.
Припустимо, що b – складова кількість. Звідси маємо, що є дільник для b, який відмінний від 1 як і від b. Такий дільник позначається як b1. Необхідно, щоб умова 1< b 1 < b було виконано.
З умови видно, що ділиться на b , b ділиться на b 1 , значить, поняття ділимості виражається таким чином: a = b · qі b = b 1 · q 1 , звідки a = b 1 · (q 1 · q) , де q і q 1є цілими числами. За правилом множення цілих чисел маємо, що добуток цілих чисел – ціле число з рівністю виду a = b 1 · (q 1 · q). Видно, що b 1 – це дільник числа а. Нерівність 1< b 1 < b невідповідає, тому що отримаємо, що b є найменшим позитивним та відмінним від 1 дільником а.
Теорема 2
Простих чисел дуже багато.
Доказ 2
Імовірно візьмемо кінцеву кількість натуральних чисел n і позначимо як p1, p2, …, pn. Розглянемо варіант знаходження простого числа, відмінного від зазначених.
Приймемо на розгляд число р, яке дорівнює p1, p2, …, pn+1. Воно не дорівнює кожному з чисел, що відповідають простим числам виду p1, p2, …, pn. Число р є простим. Тоді вважається, що теорему доведено. Якщо воно складене, тоді потрібно прийняти позначення p n + 1 і показати розбіжність дільника з жодним з p 1 , p 2 , … , p n .
Якщо це було б не так, тоді, виходячи з властивості ділимості твору p 1, p 2, …, p n , отримаємо, що воно ділилося на p n + 1 . Зауважимо, що вираз p n + 1 ділиться число р дорівнює сумі p1, p2, …, pn+1. Отримаємо, що вираз p n + 1 має ділитися другий доданок цієї суми, що дорівнює 1, але це неможливо.
Видно, що може бути знайдено будь-яке просте число серед будь-якої кількості простих чисел, що задані. Звідси випливає, що простих чисел дуже багато.
Так як простих чисел дуже багато, то таблиці обмежують числами 100 1000 10000 і так далі.
При складанні таблиці простих чисел слід зважати на те, що для такого завдання необхідна послідовна перевірка чисел, починаючи з 2 до 100 . За відсутності дільника воно фіксується в таблицю, якщо вона складова, то таблицю не заноситься.
Розглянемо покроково.
Якщо почати з числа 2, воно має тільки 2 дільника: 2 і 1, значить, його можна занести в таблицю. Також із числом 3 . Число 4 є складовим, слід розкласти його ще на 2 та 2 . Число 5 є простим, отже, можна зафіксувати у таблиці. Так виконувати до числа 100 .
Цей спосіб незручний і довгий. Таблицю скласти можна, але доведеться витратити багато часу. Необхідно використовувати ознаки подільності, які прискорять процес знаходження дільників.
Спосіб за допомогою решета Ератосфена вважають найзручнішим. Розглянемо з прикладу таблиць, наведених нижче. Для початку записуються числа 2, 3, 4, …, 50.
Тепер необхідно закреслити всі числа, які є кратними 2 . Провести послідовне закреслення. Отримаємо таблицю виду:
Переходимо до викреслювання чисел, кратних 5 . Отримаємо:
Викреслюємо числа, кратні 7, 11 . Зрештою таблиця набуває вигляду
Перейдемо до формулювання теореми.
Теорема 3
Найменший позитивний та відмінний від 1 дільник основного числа а не перевищує a , де a є арифметичним коренем заданого числа.
Доказ 3
Необхідно позначити найменший дільник складового числа а. Існує таке ціле число q де a = b · q , причому маємо, що b ≤ q . Неприпустима нерівність виду b > q,оскільки відбувається порушення умови. Обидві частини нерівності b ≤ q слід помножити на будь-яке позитивне число b, що не дорівнює 1 . Отримуємо, що b · b ≤ b · q , де b 2 ≤ a та b ≤ a .
З доведеної теореми видно, що викреслення чисел у таблиці призводить до того, що необхідно починати з числа, яке дорівнює b 2 і задовольняє нерівність b 2 a . Тобто, якщо викреслити числа, кратні 2 , процес починається з 4 , а кратних 3 - з 9 і так далі до 100 .
Упорядкування такої таблиці з допомогою теореми Ератосфена свідчить, що з викресленні всіх складових чисел, залишаться прості, які перевищують n . У прикладі, де n = 50 , ми маємо, що n = 50 . Звідси й отримуємо, що решето Ератосфена відсіює всі складові числа, які за значенням не більші за значення кореня з 50 . Пошук чисел здійснюється за допомогою викреслення.
Перед рішенням необхідно з'ясовувати, чи є число простим чи складовим. Найчастіше використовуються ознаки подільності. Розглянемо це на наведених нижче прикладі.
Приклад 1
Довести, що число 898989898989898989 є складовим.
Рішення
Сума цифр заданого числа дорівнює 9 · 8 + 9 · 9 = 9 · 17. Значить, число 9 · 17 ділиться на 9 виходячи з ознаки ділимості на 9 . Звідси випливає, що вона складова.
Такі ознаки неспроможні довести простоту числа. Якщо потрібна перевірка, слід виконувати інші дії. Найкращий спосіб - це перебір чисел. Протягом процесу можна знайти прості та складові числа. Тобто числа за значенням не повинні перевищувати a. Тобто, число а необхідно розкласти на прості множники. якщо це буде виконано, тоді число можна вважати простим.
Приклад 2
Визначити складне чи просте число 11723 .
Рішення
Тепер потрібно знайти всі дільники для числа 11723 . Необхідно оцінити 11723 .
Звідси бачимо, що 11723< 200 , то 200 2 = 40 000 , а 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Для більш точної оцінки числа 11723 необхідно записати вираз 1082 = 11664 а 109 2 = 11 881 , то 108 2 < 11 723 < 109 2 . Звідси випливає, що 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
При розкладі отримаємо, що 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 7, 7 , 89, 97, 101, 103, 107 - це все прості числа. Весь цей процес можна зобразити як поділ стовпчиком. Тобто поділити 11723 на 19 . Число 19 є одним з його множників, оскільки отримаємо поділ без залишку. Зобразимо поділ стовпчиком:
Звідси випливає, що 11723 є складовим числом, оскільки крім себе і має дільник 19 .
Відповідь: 11723 є складовим числом.
Якщо ви помітили помилку в тексті, будь ласка, виділіть її та натисніть Ctrl+Enter
Таблиця простих чисел від 1 до 10 000. Таблиця простих чисел від 1 до 1000
Нижче наведено таблицю простих чисел від 2 до 10000 (1229 штук). Одиниця не включена, вибачте. Дехто вважає, що одиниця не включена оскільки… вона й не може бути там. " Простим числом називаються числа, що мають два дільники: одиницю і саме число.А число 1 має тільки один дільник, воно не відноситься ні до простих, ні до складових чисел.Ми, тим не менш, пам'ятаємо, що прості числа вводяться іноді й так: Простим числом називаються числа, які діляться націло на одиницю і саме себе.У цьому випадку одиниця, очевидно, є простим числом.
Таблиця простих чисел від 2 до 1000. Таблиця простих чисел від 2 до 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 |
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 | 3581 | 3583 | 3593 | 3607 |
3613 | 3617 | 3623 | 3631 | 3637 | 3643 | 3659 | 3671 | 3673 | 3677 | 3691 | 3697 |
3701 | 3709 | 3719 | 3727 | 3733 | 3739 | 3761 | 3767 | 3769 | 3779 | 3793 | 3797 |
3803 | 3821 | 3823 | 3833 | 3847 | 3851 | 3853 | 3863 | 3877 | 3881 | 3889 | 3907 |
3911 | 3917 | 3919 | 3923 | 3929 | 3931 | 3943 | 3947 | 3967 | 3989 | 4001 | 4003 |
4007 | 4013 | 4019 | 4021 | 4027 | 4049 | 4051 | 4057 | 4073 | 4079 | 4091 | 4093 |
4099 | 4111 | 4127 | 4129 | 4133 | 4139 | 4153 | 4157 | 4159 | 4177 | 4201 | 4211 |
4217 | 4219 | 4229 | 4231 | 4241 | 4243 | 4253 | 4259 | 4261 | 4271 | 4273 | 4283 |
4289 | 4297 | 4327 | 4337 | 4339 | 4349 | 4357 | 4363 | 4373 | 4391 | 4397 | 4409 |
4421 | 4423 | 4441 | 4447 | 4451 | 4457 | 4463 | 4481 | 4483 | 4493 | 4507 | 4513 |
4517 | 4519 | 4523 | 4547 | 4549 | 4561 | 4567 | 4583 | 4591 | 4597 | 4603 | 4621 |
4637 | 4639 | 4643 | 4649 | 4651 | 4657 | 4663 | 4673 | 4679 | 4691 | 4703 | 4721 |
4723 | 4729 | 4733 | 4751 | 4759 | 4783 | 4787 | 4789 | 4793 | 4799 | 4801 | 4813 |
4817 | 4831 | 4861 | 4871 | 4877 | 4889 | 4903 | 4909 | 4919 | 4931 | 4933 | 4937 |
4943 | 4951 | 4957 | 4967 | 4969 | 4973 | 4987 | 4993 | 4999 | 5003 | 5009 | 5011 |
5021 | 5023 | 5039 | 5051 | 5059 | 5077 | 5081 | 5087 | 5099 | 5101 | 5107 | 5113 |
5119 | 5147 | 5153 | 5167 | 5171 | 5179 | 5189 | 5197 | 5209 | 5227 | 5231 | 5233 |
5237 | 5261 | 5273 | 5279 | 5281 | 5297 | 5303 | 5309 | 5323 | 5333 | 5347 | 5351 |
5381 | 5387 | 5393 | 5399 | 5407 | 5413 | 5417 | 5419 | 5431 | 5437 | 5441 | 5443 |
5449 | 5471 | 5477 | 5479 | 5483 | 5501 | 5503 | 5507 | 5519 | 5521 | 5527 | 5531 |
5557 | 5563 | 5569 | 5573 | 5581 | 5591 | 5623 | 5639 | 5641 | 5647 | 5651 | 5653 |
5657 | 5659 | 5669 | 5683 | 5689 | 5693 | 5701 | 5711 | 5717 | 5737 | 5741 | 5743 |
5749 | 5779 | 5783 | 5791 | 5801 | 5807 | 5813 | 5821 | 5827 | 5839 | 5843 | 5849 |
5851 | 5857 | 5861 | 5867 | 5869 | 5879 | 5881 | 5897 | 5903 | 5923 | 5927 | 5939 |
5953 | 5981 | 5987 | 6007 | 6011 | 6029 | 6037 | 6043 | 6047 | 6053 | 6067 | 6073 |
6079 | 6089 | 6091 | 6101 | 6113 | 6121 | 6131 | 6133 | 6143 | 6151 | 6163 | 6173 |
6197 | 6199 | 6203 | 6211 | 6217 | 6221 | 6229 | 6247 | 6257 | 6263 | 6269 | 6271 |
6277 | 6287 | 6299 | 6301 | 6311 | 6317 | 6323 | 6329 | 6337 | 6343 | 6353 | 6359 |
6361 | 6367 | 6373 | 6379 | 6389 | 6397 | 6421 | 6427 | 6449 | 6451 | 6469 | 6473 |
6481 | 6491 | 6521 | 6529 | 6547 | 6551 | 6553 | 6563 | 6569 | 6571 | 6577 | 6581 |
6599 | 6607 | 6619 | 6637 | 6653 | 6659 | 6661 | 6673 | 6679 | 6689 | 6691 | 6701 |
6703 | 6709 | 6719 | 6733 | 6737 | 6761 | 6763 | 6779 | 6781 | 6791 | 6793 | 6803 |
6823 | 6827 | 6829 | 6833 | 6841 | 6857 | 6863 | 6869 | 6871 | 6883 | 6899 | 6907 |
6911 | 6917 | 6947 | 6949 | 6959 | 6961 | 6967 | 6971 | 6977 | 6983 | 6991 | 6997 |
7001 | 7013 | 7019 | 7027 | 7039 | 7043 | 7057 | 7069 | 7079 | 7103 | 7109 | 7121 |
7127 | 7129 | 7151 | 7159 | 7177 | 7187 | 7193 | 7207 | 7211 | 7213 | 7219 | 7229 |
7237 | 7243 | 7247 | 7253 | 7283 | 7297 | 7307 | 7309 | 7321 | 7331 | 7333 | 7349 |
7351 | 7369 | 7393 | 7411 | 7417 | 7433 | 7451 | 7457 | 7459 | 7477 | 7481 | 7487 |
7489 | 7499 | 7507 | 7517 | 7523 | 7529 | 7537 | 7541 | 7547 | 7549 | 7559 | 7561 |
7573 | 7577 | 7583 | 7589 | 7591 | 7603 | 7607 | 7621 | 7639 | 7643 | 7649 | 7669 |
7673 | 7681 | 7687 | 7691 | 7699 | 7703 | 7717 | 7723 | 7727 | 7741 | 7753 | 7757 |
7759 | 7789 | 7793 | 7817 | 7823 | 7829 | 7841 | 7853 | 7867 | 7873 | 7877 | 7879 |
7883 | 7901 | 7907 | 7919 | 7927 | 7933 | 7937 | 7949 | 7951 | 7963 | 7993 | 8009 |
8011 | 8017 | 8039 | 8053 | 8059 | 8069 | 8081 | 8087 | 8089 | 8093 | 8101 | 8111 |
8117 | 8123 | 8147 | 8161 | 8167 | 8171 | 8179 | 8191 | 8209 | 8219 | 8221 | 8231 |
8233 | 8237 | 8243 | 8263 | 8269 | 8273 | 8287 | 8291 | 8293 | 8297 | 8311 | 8317 |
8329 | 8353 | 8363 | 8369 | 8377 | 8387 | 8389 | 8419 | 8423 | 8429 | 8431 | 8443 |
8447 | 8461 | 8467 | 8501 | 8513 | 8521 | 8527 | 8537 | 8539 | 8543 | 8563 | 8573 |
8581 | 8597 | 8599 | 8609 | 8623 | 8627 | 8629 | 8641 | 8647 | 8663 | 8669 | 8677 |
8681 | 8689 | 8693 | 8699 | 8707 | 8713 | 8719 | 8731 | 8737 | 8741 | 8747 | 8753 |
8761 | 8779 | 8783 | 8803 | 8807 | 8819 | 8821 | 8831 | 8837 | 8839 | 8849 | 8861 |
8863 | 8867 | 8887 | 8893 | 8923 | 8929 | 8933 | 8941 | 8951 | 8963 | 8969 | 8971 |
8999 | 9001 | 9007 | 9011 | 9013 | 9029 | 9041 | 9043 | 9049 | 9059 | 9067 | 9091 |
9103 | 9109 | 9127 | 9133 | 9137 | 9151 | 9157 | 9161 | 9173 | 9181 | 9187 | 9199 |
9203 | 9209 | 9221 | 9227 | 9239 | 9241 | 9257 | 9277 | 9281 | 9283 | 9293 | 9311 |
9319 | 9323 | 9337 | 9341 | 9343 | 9349 | 9371 | 9377 | 9391 | 9397 | 9403 | 9413 |
9419 | 9421 | 9431 | 9433 | 9437 | 9439 | 9461 | 9463 | 9467 | 9473 | 9479 | 9491 |
9497 | 9511 | 9521 | 9533 | 9539 | 9547 | 9551 | 9587 | 9601 | 9613 | 9619 | 9623 |
9629 | 9631 | 9643 | 9649 | 9661 | 9677 | 9679 | 9689 | 9697 | 9719 | 9721 | 9733 |
9739 | 9743 | 9749 | 9767 | 9769 | 9781 | 9787 | 9791 | 9803 | 9811 | 9817 | 9829 |
9833 | 9839 | 9851 | 9857 | 9859 | 9871 | 9883 | 9887 | 9901 | 9907 | 9923 | 9929 |
9931 | 9941 | 9949 | 9967 | 9973 | кінець таблички 🙂! |
Оцінка статті:
У цій статті ми вивчимо прості та складові числа. Спочатку дамо визначення простих і складових чисел, а також наведемо приклади. Після цього доведемо, що простих чисел дуже багато. Далі запишемо таблицю простих чисел і розглянемо методи складання таблиці простих чисел, особливо ретельно зупинимося на способі, що отримав назву решето Ератосфена. Насамкінець висвітлимо основні моменти, які потрібно враховувати при доказі того, що дане число є простим або складовим.
Навігація на сторінці.
Прості та складові числа – визначення та приклади
Поняття прості числа та складові числа відносяться до , що більше одиниці. Такі цілі числа, залежно кількості їх позитивних дільників, поділяються на прості і складові числа. Таким чином, щоб зрозуміти визначення простих та складових чисел, потрібно добре уявляти собі, що таке дільники та кратні.
Визначення.
Прості числа- Це цілі числа, великі одиниці, які мають тільки два позитивні дільники, а саме самих себе і 1 .
Визначення.
Складові числа– це цілі числа, великі одиниці, яке мають принаймні три позитивні дільники.
Окремо зауважимо, що число 1 не відноситься до простих, ні до складових чисел. Одиниця має лише один позитивний дільник, яким є саме число 1 . Цим число 1 відрізняється від решти цілих позитивних чисел, які мають не менше двох позитивних дільників.
З огляду на те, що цілі позитивні числа – це , і що одиниця має лише один позитивний дільник, можна навести інші формулювання озвучених визначень простих і складових чисел.
Визначення.
Простими числаминазивають натуральні числа, які мають лише два позитивні дільники.
Визначення.
Складовими числаминазивають натуральні числа, що мають понад два позитивні дільники.
Зазначимо, що кожне ціле позитивне число, більше одиниці, є або простим, або складовим числом. Іншими словами, немає жодного такого цілого числа, яке не було б ні простим, ні складовим. Це випливає з властивості ділимості, Що свідчить, що числа 1 і a завжди є дільниками будь-якого цілого числа a .
Виходячи з інформації попереднього абзацу, можна надати таке визначення складових чисел.
Визначення.
Натуральні числа, які не є простими, називаються складовими.
Наведемо приклади простих та складових чисел.
Як приклади складових чисел наведемо 6 , 63 , 121 і 6 697 . Це твердження теж потребує пояснення. Число 6 має крім позитивних дільників 1 і 6 ще й дільники 2 і 3, так як 6 = 2 · 3 тому 6 - дійсно складове число. Позитивними дільниками 63 є числа 1, 3, 7, 9, 21 та 63. Число 121 дорівнює добутку 11 · 11 тому його позитивними дільниками є 1 , 11 і 121 . А число 6697 складене, так як його позитивними дільниками крім 1 і 6697 є ще й числа 37 і 181 .
На закінчення цього пункту хочеться ще звернути увагу на те, що прості числа і взаємно прості числа– це далеко жодне й те саме.
Таблиця простих чисел
Прості числа для зручності їх подальшого використання записують у таблицю, яку називають таблицею простих чисел. Нижче представлена таблиця простих чиселдо 1000 .
Виникає логічне запитання: «Чому ми заповнили таблицю простих чисел лише до 1 000, хіба не можна скласти таблицю всіх простих чисел»?
Відповімо спочатку на першу частину цього питання. Для більшості завдань, при вирішенні яких доведеться використовувати прості числа, нам буде досить простих чисел в межах тисячі. В інших випадках, швидше за все, доведеться вдаватися до якихось спеціальних прийомів рішення. Хоча, безсумнівно, ми можемо скласти таблицю простих чисел до скільки завгодно великого кінцевого цілого позитивного числа, чи то 10 000 або 1 000 000 000 , в наступному пункті ми поговоримо про методи складання таблиць простих чисел, зокрема, розберемо спосіб, що отримав назву.
Тепер розберемося з можливістю (а точніше, з неможливістю) складання таблиці всіх існуючих простих чисел. Ми не можемо скласти таблицю всіх простих чисел, тому що простих чисел дуже багато. Останнє твердження є теоремою, яку ми доведемо після наступної допоміжної теореми.
Теорема.
Найменший позитивний і відмінний від 1 дільник натурального числа, більшого за одиницю, є простим числом.
Доведення.
Нехай a – натуральне число, більше одиниці, і b – найменший позитивний і відмінний від одиниці дільник числа a . Доведемо, що b – просте число шляхом протилежного.
Припустимо, що b – складова кількість. Тоді існує дільник числа b (позначимо його b 1), який відмінний як від 1, так і від b. Якщо врахувати, що абсолютна величина дільника не перевищує абсолютної величини ділимого (це ми знаємо з властивостей ділимості), то повинна виконуватися умова 1
Так як число a ділиться на b за умовою, і ми сказали, що b ділиться на b 1 то поняття ділимості дозволяє говорити про існування таких цілих чисел q і q 1 , що a = b · q і b = b 1 · q 1 , Звідки a = b 1 · (q 1 · q) . З випливає, що добуток двох цілих чисел є цілим числом, тоді рівність a=b 1 ·(q 1 ·q) вказує на те, що b 1 є дільником числа a . Враховуючи отримані вище нерівності 1
Тепер ми можемо довести, що простих чисел дуже багато.
Теорема.
Простих чисел дуже багато.
Доведення.
Припустимо, що це негаразд. Тобто, припустимо, що простих чисел всього n штук і ці прості числа є p 1 , p 2 , ..., p n . Покажемо, що ми завжди можемо знайти просте число, відмінне від зазначених.
Розглянемо число, що дорівнює p 1 · p 2 · ... · p n +1 . Зрозуміло, що це число відрізняється від кожного з простих чисел p 1 , p 2 ..., p n . Якщо число p - просте, теорема доведена. Якщо це число складене, то з попередньої теореми існує простий дільник цього числа (позначимо його p n+1 ). Покажемо, що це дільник не збігається з жодним із чисел p 1 , p 2 , …, p n .
Якби це було не так, то за властивостями ділимості добуток p 1 · p 2 · ... p n ділилося б на p n +1 . Але на p n+1 ділиться і число p , що дорівнює сумі p 1 · p 2 · ... · p n +1 . Звідси випливає, що на p n+1 має ділитися другий доданок цієї суми, який дорівнює одиниці, а це неможливо.
Так доведено, що завжди може бути знайдене нове просте число, яке не полягає серед будь-якої кількості наперед заданих простих чисел. Отже, простих чисел дуже багато.
Отже, через те, що простих чисел нескінченно багато, при складанні таблиць простих чисел завжди обмежують себе зверху будь-яким числом, зазвичай, 100 , 1 000 , 10 000 і т.д.
Решето Ератосфена
Нині ми обговоримо способи складання таблиць простих чисел. Припустимо, що потрібно скласти таблицю простих чисел до 100 .
Найочевиднішим методом вирішення цього завдання є послідовна перевірка цілих позитивних чисел, починаючи з 2 і закінчуючи 100 на наявність позитивного дільника, який більше 1 і менше перевіряється числа (з властивостей ділимості ми знаємо, що абсолютна величина дільника не перевищує абсолютної величини дел відмінного від нуля). Якщо такий дільник не знайдено, то число, що перевіряється, є простим, і воно заноситься в таблицю простих чисел. Якщо ж такий дільник знайдений, то число, що перевіряється, є складовим, воно не заноситься в таблицю простих чисел. Після цього відбувається перехід до наступного числа, що аналогічно перевіряється на наявність дільника.
Опишемо кілька перших кроків.
Починаємо з числа 2 . Число 2 немає позитивних дільників, крім 1 і 2 . Отже, воно просте, тому заносимо його в таблицю простих чисел. Тут слід сказати, що 2 є найменшим простим числом. Переходимо до 3 . Його можливим позитивним дільником, відмінним від 1 і 3 є число 2 . Але 3 на 2 не ділиться, тому, 3 - просте число, і його також потрібно занести до таблиці простих чисел. Переходимо до 4 . Його позитивними дільниками, відмінними від 1 і 4 можуть бути числа 2 і 3, перевіримо їх. Число 4 ділиться на 2, тому, 4 – складове число, і його не потрібно заносити до таблиці простих чисел. Звернімо увагу, що 4 – найменше складове число. Переходимо до 5 . Перевіряємо, чи є його дільником хоч одне з чисел 2 , 3 , 4 . Так як 5 не ділиться ні на 2, ні на 3, ні на 4, то воно просте, і його треба записати в таблицю простих чисел. Далі відбувається перехід до числа 6 , 7 і так далі до 100 .
Такий підхід до складання таблиці простих чисел далеко не ідеальний. Так чи інакше він має право на існування. Зазначимо, що при цьому способі побудови таблиці цілих чисел можна використовувати ознаки подільності, які трохи прискорять процес пошуку дільників
Існує зручніший спосіб для складання таблиці простих чисел, званий . Присутнє у назві слово «решето» невипадково, оскільки дії цього методу допомагають хіба що «просіяти» крізь решето Ератосфена цілі числа, великі одиниці, щоб відокремити прості від складових.
Покажемо решето Ератосфена у дії під час складання таблиці простих чисел до 50 .
Спочатку записуємо по порядку числа 2, 3, 4, …, 50 .
Перше записане число 2 є простим. Тепер від числа 2 послідовно переміщуємось праворуч на два числа і закреслюємо ці числа, поки не дістанемося до кінця таблиці чисел, що складається. Так буде викреслено всі числа, кратні двом.
Першим наступним за 2 невикресленим числом є 3 . Це число просте. Тепер від числа 3 послідовно переміщуємось праворуч на три числа (враховуючи і вже закреслені числа) і викреслюємо їх. Так буде викреслено всі числа, кратні трьом.
Першим наступним за 3 невикресленим числом є 5 . Це число просте. Тепер від числа 5 послідовно переміщуємось праворуч на 5 чисел (враховуємо і закреслені раніше числа) і викреслюємо їх. Так буде викреслено всі числа, кратні п'яти.
Далі викреслюємо числа, кратні 7 потім, кратні 11 і так далі. Процес закінчується, коли залишиться чисел для викреслення. Нижче показана закінчена таблиця простих чисел до 50 отримана за допомогою решета Ератосфена. Усі незакреслені числа є простими, проте закреслені числа – складовими.
Давайте ще сформулюємо та доведемо теорему, яка дозволить прискорити процес складання таблиці простих чисел за допомогою решета Ератосфена.
Теорема.
Найменший позитивний і відмінний від одиниці дільник складового числа a вбирається у , де - з a .
Доведення.
Позначимо літерою b найменший і відмінний від одиниці дільник складового числа a (число b є простим, що випливає з теореми, доведеної на початку попереднього пункту). Тоді існує таке ціле число q , що a=b·q (тут q – позитивне ціле число, що випливає з правил множення цілих чисел), причому (при b>q порушиться умова, що b – найменший дільник числа a , оскільки q також є дільником числа a через рівність a=q·b ). Помноживши обидві частини нерівності на позитивне і більше одиниці ціле число b (це дозволяють зробити ), отримуємо , звідки і .
Що ж нам дає доведена теорема щодо решета Ератосфена?
По-перше, викреслення складових чисел, кратних простому числу b слід починати з числа, рівного (це випливає з нерівності). Наприклад, викреслення чисел, кратних двом, слід починати з числа 4, кратних трьом – з числа 9, кратних п'яти – з числа 25 і так далі.
По-друге, складання таблиці простих чисел до числа n за допомогою решета Ератосфена можна вважати закінченим тоді, коли будуть викреслені всі складові числа, кратні простим числам, що не перевищують . У нашому прикладі n=50 (оскільки ми складаємо таблицю простих чисел до 50 ) і тому решето Ератосфена має відсіяти всі складові числа, кратні простим числам 2 , 3 , 5 і 7 , які не перевищують арифметичного квадратного кореня з 50 . Тобто, нам далі не потрібно займатися пошуком і викресленням чисел, кратних простим числам 11, 13, 17, 19, 23 і так далі до 47, тому що вони вже будуть викреслені, як кратні меншим простим числам 2, 3, 5 і 7 .
Дана кількість проста чи складова?
Деякі завдання вимагають з'ясування, чи це число простим чи складним. У загальному випадку це завдання далеко не просте, особливо для чисел, запис яких складається із значної кількості знаків. Найчастіше доводиться шукати який-небудь специфічний спосіб її вирішення. Однак ми спробуємо дати напрямок ходу думок для нескладних випадків.
Безперечно, можна спробувати скористатися ознаками подільності для доказу того, що це число є складовим. Якщо, наприклад, певний ознака ділимості показує, що це число ділиться на деяке ціле позитивне число більше одиниці, то вихідне число є складовим.
приклад.
Доведіть, що число 898989898989898989 складне.
Рішення.
Сума цифр цього числа дорівнює 9 · 8 +9 · 9 = 9 · 17 . Так як число, що дорівнює 9 · 17 ділиться на 9, то по ознакою подільності на 9можна стверджувати, що вихідне число також поділяється на 9 . Отже, воно є складовим.
Істотний недолік такого підходу у тому, що ознаки ділимості неможливо довести простоту числа. Тому при перевірці числа на те, чи воно є простим чи складовим, потрібно діяти інакше.
Найлогічніший підхід полягає у переборі всіх можливих дільників цього числа. Якщо жоден із можливих дільників нічого очікувати справжнім дільником цього числа, це число буде простим, інакше – складовим. З теорем, доведених у попередньому пункті, випливає, що дільники даного числа a потрібно шукати серед простих чисел, що не перевищують . Таким чином, це число a можна послідовно ділити на прості числа (які зручно брати з таблиці простих чисел), намагаючись знайти дільник числа a . Якщо знайдено дільник, то число a – складове. Якщо ж серед простих чисел, що не перевершують , не виявиться дільник числа a, то число a - просте.
приклад.
Число 11 723 просте чи складове?
Рішення.
З'ясуємо, до якого простого числа можуть бути дільники числа 11723 . Для цього оцінимо.
Досить очевидно, що , так як 2002 = 40000, а 11723<40 000
(при необходимости смотрите статью порівняння чисел). Таким чином, можливі прості дільники числа 11723 менше числа 200 . Це вже значно полегшує наше завдання. Якби ми цього не знали, то нам довелося б перебирати всі прості числа не до 200 , а аж до числа 11 723 .
За бажання можна оцінити більш точно. Оскільки 108 2 =11 664 , а 109 2 =11 881 , то 108 2<11 723<109 2
, следовательно, . Таким чином, будь-яке з простих чисел, менших 109 потенційно є простим дільником даного числа 11 723 .
Тепер ми будемо послідовно ділити число 11 723 на прості числа 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 7 6 , 5 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Якщо число 11723 розділиться націло на одне із записаних простих чисел, то воно буде складовим. Якщо ж воно не ділиться на жодне із записаних простих чисел, то вихідне число просте.
Не описуватимемо весь цей монотонний і одноманітний процес поділу. Відразу скажемо, що 11 723