ПРОСТІ ТА СКЛАДЕНІ ЧИСЛА
Ератосфен (Ερατοσθένης, Eratosthenes) (бл. 275 — 194 до н. е.), давньогрецький вчений і письменник. Один із надзвичайно різнобічних вчених античності. Ератосфен займався філологією, філософією, хронологією, математикою, астрономією, геодезією, географією, сам писав вірші і музику. За це сучасники дали йому прізвисько Пентатл, тобто Багатоборець. Інше його прізвисько, Бета, тобто «другий», очевидно, свідчило про те, що у всіх науках Ератосфен досягає не найвищого, але чудового результату.
Просте число
Просте число — це натуральне число, яке має рівно два різних натуральних дільники (лише 1 і саме число).
Послідовність простих чисел починається так: 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, …
Складене число
Складене число — натуральне число, яке більше 1 і не є простим. Кожне складене число є добутком двох натуральних чисел, більших 1.
Послідовність складених чисел починається так: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, …
Будь-яке складене число може бути єдиним чином розкладене в добуток простих множників.
Основна теорема арифметики
Будь-яке натуральне число більше одиниці може бути представлене у вигляді добутку простих чисел і таке представлення є єдиним з точністю до порядку множників.
Розклад натуральних чисел на добуток простих
Представлення натурального числа у вигляді добутку простих називають розкладом на прості абофакторизацією числа.
Розклад заданого числа на прості множники
Подає складене натуральне число у вигляді добутку простих чисел

Ератосфен

Життя
Ератосфен народився в Африці, у Кірені. Навчався спочатку в Александрії, можливо, у Каллімаха, а потім в Афінах у відомих наставників, Зенона Кіфеонського, платоніка Аркесілая і перипатетика Арістона з Хіоса, граматика Лісанія. Імовірно, саме завдяки настільки широкій освіті і розмаїтості інтересів бл. 245 до н. е. Ератосфен отримав від Птолемея III Евергета запрошення повернутися в Александрію, щоб стати вихователем спадкоємця престолу (згодом Птолемея IV Філопатра) й очолити Александрійську бібліотеку. Ератосфен пристав на цю пропозицію й обіймав посаду бібліотекаря до кінця життя. Його наукові таланти удостоїлися високої оцінки сучасника Ератосфена, Архімеда, який присвятив йому свою книгу Ефодик (тобто Метод).
Ератосфен народився в Африці, у Кірені. Навчався спочатку в Александрії, можливо, у Каллімаха, а потім в Афінах у відомих наставників, Зенона Кіфеонського, платоніка Аркесілая і перипатетика Арістона з Хіоса, граматика Лісанія. Імовірно, саме завдяки настільки широкій освіті і розмаїтості інтересів бл. 245 до н. е. Ератосфен отримав від Птолемея III Евергета запрошення повернутися в Александрію, щоб стати вихователем спадкоємця престолу (згодом Птолемея IV Філопатра) й очолити Александрійську бібліотеку. Ератосфен пристав на цю пропозицію й обіймав посаду бібліотекаря до кінця життя. Його наукові таланти удостоїлися високої оцінки сучасника Ератосфена, Архімеда, який присвятив йому свою книгу Ефодик (тобто Метод).
Математика й філософія
Серед математичних творів Ератосфена виділяється твір Платоники (Platonikos), свого роду коментар до діалога «Тімей» Платона, у якому розглядалися питання з області математики і музики. Ератосфен звертається до математичних і музичних основ платонівської філософії. Вихідним пунктом було так зване делійське питання, тобто подвоєння куба, якому автор присвятив трактат Подвоєння куба. Геометричний зміст мав твір Про середні величини (Peri mesotenon) у 2 частинах, присвячений розв'язуванню геометричних та арифметичних задач. Широко відомий трактат Решето (Koskonon). В ньому вчений виклав спрощену методику визначення простих чисел (так зване «решето Ератосфена»).
Серед математичних творів Ератосфена виділяється твір Платоники (Platonikos), свого роду коментар до діалога «Тімей» Платона, у якому розглядалися питання з області математики і музики. Ератосфен звертається до математичних і музичних основ платонівської філософії. Вихідним пунктом було так зване делійське питання, тобто подвоєння куба, якому автор присвятив трактат Подвоєння куба. Геометричний зміст мав твір Про середні величини (Peri mesotenon) у 2 частинах, присвячений розв'язуванню геометричних та арифметичних задач. Широко відомий трактат Решето (Koskonon). В ньому вчений виклав спрощену методику визначення простих чисел (так зване «решето Ератосфена»).
Решето́ Ератосфе́на в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа n, що був створений давньогрецьким математиком Ератосфеном. Він є попередником сучасного решета Аткіна, швидшого, але і складнішого алгоритму.
Метод
Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N2 -1. Потім в цьому ряду викреслюються всі числа, які діляться на 2,3, 4 і так далі до N. Числа, які залишилися невикресленими після цієї процедури - прості.
Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N2 -1. Потім в цьому ряду викреслюються всі числа, які діляться на 2,3, 4 і так далі до N. Числа, які залишилися невикресленими після цієї процедури - прості.
Алгоритм (ілюструється анімованим зображенням)
Зробимо список чисел від 2 до найбільшого, про яке хочемо дізнатися чи є простим (дивіться також Тест простоти). Назвемо його Список А. (Це таблиця в лівій частині зображення.)
Запишемо число 2, перше просте число, в інший список для знайдених простих чисел. Назвемо його Список В. (Це список в правій частині зображення.)
Викреслимо 2 і всі кратні 2 числа зі Списку А.
Перше (найменше) невикреслене число в Списку А є простим. Запишемо його в Список В.
Викреслимо це число і всі кратні йому числа зі Списку А. Викреслювання кратних можна почати з числа, яке є квадратом поточного простого числа, бо менші кратні були викреслені на попередньому кроці (наприклад, 6 було викреслене як 2*3 і викреслювати його як 3*2 вже не треба, тобто починаємо з 3*3=32).
Повторюємо кроки 4 і 5 до тих пір, поки в Списку А не залишиться чисел.
Зробимо список чисел від 2 до найбільшого, про яке хочемо дізнатися чи є простим (дивіться також Тест простоти). Назвемо його Список А. (Це таблиця в лівій частині зображення.)
Запишемо число 2, перше просте число, в інший список для знайдених простих чисел. Назвемо його Список В. (Це список в правій частині зображення.)
Викреслимо 2 і всі кратні 2 числа зі Списку А.
Перше (найменше) невикреслене число в Списку А є простим. Запишемо його в Список В.
Викреслимо це число і всі кратні йому числа зі Списку А. Викреслювання кратних можна почати з числа, яке є квадратом поточного простого числа, бо менші кратні були викреслені на попередньому кроці (наприклад, 6 було викреслене як 2*3 і викреслювати його як 3*2 вже не треба, тобто починаємо з 3*3=32).
Повторюємо кроки 4 і 5 до тих пір, поки в Списку А не залишиться чисел.
Немає коментарів:
Дописати коментар