Студопедия — Нескінченість множини простих чисел. Решето Ератосфена.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Нескінченість множини простих чисел. Решето Ератосфена.






Давньогрецьких вчених зацікавило: скільки може бути простих чисел в натуральному ряді? Відповів на це питання Евклід, довівши, що множина простих чисел нескінченна.

Теорема 2.1 (Евкліда). Множина простих чисел нескінченна.

□ Припустимо, що множина простих чисел скінчена. Нехай вона складається з простих чисел p1, p2,..., рп. Отже, ми припускаємо, що простих чисел, відмінних від p1, p2,..., рп, немає. Розглянемо тепер ціле число р = p1 p2,... рп. Очевидно, що це число відмінне від кожного з чисел p1, p2,..., рп. Оскільки число 1 не має дільників, відмінних від самого себе, то жодне з простих чисел p1, p2,..., рп не може бути дільником числа р. Ціле число р > 1. Тому воно або само просте, або за теоремою 3 ділиться на просте число, відмінне від кожного з чисел p1, p2,..., рп Звідси випливає, що існує принаймні одне просте число, відмінне від чисел p1, p2,..., рп а це суперечить нашому припущенню. Отже, наше припущення неправильне. Цим теорему доведено. ■

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

Таблицю всіх простих чисел, що не перевищують даного натурального числа N, можна скласти так. Випишемо підряд усі натуральні числа від 2 до N:

2, 3, 4, 5,..., N (1)

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

Уперше для складання таблиць простих чисел описаний щойно метод застосував грецький математик Ератосфен. Ератосфен писав числа на папірусі, натягнутому на рамку; числа він не закреслював, а проколював. Внаслідок цього він діставав дещо схоже на решето: складені числа «просіювалися» крізь це решето, а прості числа залишалися. Тому цей метод називають решетом Ератосфена.

Метод Ератосфена поступово удосконалювався, завдяки чому складання таблиць простих чисел спрощувалося. Це, в свою чергу, дало можливість скласти таблиці простих чисел, що містять порівняно велику кількість чисел. Тепер складені таблиці простих чисел приблизно до 10 мільйонів.

Приклад 1. Знайти прості чиста на проміжку [2, 30].

Запишемо натуральні числа починаючи від 2 до 30 в ряд:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Перше число у списку, 2 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 2 (тобто кожне друге, починаючи з 22 = 4):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Наступне незакреслене число 3 - просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 3 (тобто кожне третє, починаючи з 32 = 9):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Наступне незакреслене число 5 - Просте. Пройдемо по ряду чисел, закреслюючи всі числа кратні 5 (тобто кожне п'яте, починаючи з 2 5 = 25). І т. д.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Необхідно провести закреслення кратних для всіх простих чисел p, Для яких p 2 ≤ n. У результаті всі складені числа будуть закреслені, а незакресленими залишаться всі прості числа. Для n =30 вже після закреслення кратних числу 5 всі складені числа виходять закресленими:

2 3 5 7 11 13 17 19 23 29

Отримали всі прості числа на даному проміжку.

 







Дата добавления: 2015-08-12; просмотров: 871. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

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

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Этапы и алгоритм решения педагогической задачи Технология решения педагогической задачи, так же как и любая другая педагогическая технология должна соответствовать критериям концептуальности, системности, эффективности и воспроизводимости...

Понятие и структура педагогической техники Педагогическая техника представляет собой важнейший инструмент педагогической технологии, поскольку обеспечивает учителю и воспитателю возможность добиться гармонии между содержанием профессиональной деятельности и ее внешним проявлением...

Репродуктивное здоровье, как составляющая часть здоровья человека и общества   Репродуктивное здоровье – это состояние полного физического, умственного и социального благополучия при отсутствии заболеваний репродуктивной системы на всех этапах жизни человека...

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...

ОПРЕДЕЛЕНИЕ ЦЕНТРА ТЯЖЕСТИ ПЛОСКОЙ ФИГУРЫ Сила, с которой тело притягивается к Земле, называется силой тяжести...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия