Решето эратосфена что это такое
Решето Эратосфена.
Вполне вероятно, что алгоритм, придуманный более 2000 лет назад греческим математиком Эратосфеном Киренским, был первым в своем роде. Его единственная задача – нахождение всех простых чисел до некоторого заданного числа N. Термин «решето» подразумевает фильтрацию, а именно фильтрацию всех чисел за исключением простых. Так, обработка алгоритмом числовой последовательности оставит лишь простые числа, все составные же отсеются.
Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.
| 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 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
В приведенной таблице записаны натуральные числа от 2 до 100. Красным помечены те, которые удаляются в процессе выполнения алгоритма «Решето Эратосфена».
Программная реализация алгоритма Эратосфена потребует:
- организовать логический массив и присвоить его элементам из диапазона от 2 до N логическую единицу;
- в свободную переменную P записать число 2, являющееся первым простым числом;
- исключить из массива все числа кратные P2, ступая с шагом по P;
- записать в P следующее за ним не зачеркнутое число;
- повторять действия, описанные в двух предыдущих пунктах, пока это возможно.
Обратите внимание: на третьем шаге мы исключаем числа, начиная сразу с P2, это связано с тем, что все составные числа меньшие P будут уже зачеркнуты. Поэтому процесс фильтрации следует остановить, когда P2 станет превышать N. Это важное замечание позволяет улучшить алгоритм, уменьшив число выполняемых операций.
Так будет выглядеть псевдокод алгоритма:
пока P2≤N выполнять { i←P2 если B[P]=true то пока i≤N выполнять { B[i]←false i←i+P } P←P+1 }
kvodo.ru
Решето Эратосфена, попытка минимизировать память
Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком. Картинка из википедии: 
Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут. Одна из проблем при поиске решетом это объем памяти который надо выделить под фильтруемые числа. Вычеркнутые непростые удаляются уменьшая память, но изначально объем требуется большой.
Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).
Реализация алгоритма
Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых. Суть алгоритма: Допустим мы имеем несколько уже найденных простых чисел отсортированных по возрастанию. (Алгоритм стартует с [2,3]). Для каждого из них храним последнее (наибольшее) зачеркнутое число. Инициализируем самими простыми числами. Выбираем кандидата в простые например наибольшее найденное простое число +1 (в алгоритме внизу перескакиваем четные как заведомо не простые). Кандидат сравнивается с последним зачеркнутым текущего простого. Пока текущее зачеркнутое меньше кандидата увеличиваем его на текущее простое. Если текущее зачеркнутое равно кандидату, то кандидат не простое число. Выбираем следующего кандидата. В случае если текущее зачеркнутое больше кандидата, проверяем кандидата на следующем простом числе. Если добрались до конца списка простых чисел (то есть все зачеркнутые больше кандидата) мы нашли очередное простое число. Добавляем его в список и инициализируем последнее зачеркнутое найденным простым.Код на java
import java.util.ArrayList; import java.util.List; public class SieveEratosthenes { static class PrimePair { Integer prime; Integer lastCrossed; PrimePair(Integer prime, Integer lastCrossed) { this.prime = prime; this.lastCrossed = lastCrossed; } } private List primes; private SieveEratosthenes() { primes = new ArrayList(); primes.add(new PrimePair(2, 2)); primes.add(new PrimePair(3, 3)); } private void fillNPrimes(int n) { while (primes.size()habr.com
Решето Эратосфена - алгоритм определения простых чисел
Решето Эратосфена – это алгоритм нахождения простых чисел до заданного натурального числа путем постепенного отсеивания составных чисел. Образно говоря, через решето Эратосфена в процессе его тряски проскакивают составные числа, а простые остаются в решете.
Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 2, второе простое число - это 3. Теперь начнем рассуждать:
- Все четные числа, кроме двойки, - составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
- Все числа кратные трем, кроме самой тройки, - составные, так как делятся не только на самих себя и единицу, а также еще на 3.
- Число 4 уже выбыло из игры, так как делится на 2.
- Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
- Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.
Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.
Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.
При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа n в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.
Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до n. Здесь важнее индексы, чем значения элементов. Значениями может быть True, обозначающее простое число, и False, обозначающее сложное число.
В данном примере реализации алгоритма Эратосфена список заполняется числами от 0 до n включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:
n = int(input()) # список заполняется значениями от 0 до n a = [] for i in range(n + 1): a.append(i) # Вторым элементом является единица, # которую не считают простым числом # забиваем ее нулем. a[1] = 0 # начинаем с 3-го элемента i = 2 while iyounglinux.info
Решето Эратосфена.
Для составления таблицы простых чисел, не превосходящих данного целого N, существует простой способ, называемый решетом Эратосфена. Он состоит в следующем:
1. Выписываем числа
1,2,…,N. (1)
Первое большее 1 число этого ряда есть 2. Оно делится только на 1 и на самого себя, следовательно, оно простое. Вычеркиваем из ряда (1), (как составные) все числа кратные 2, кроме самого числа 2. Первое следующее за двойкой не вычеркнутое число есть 3. Оно не делится на 2, (иначе оказалось бы вычеркнутым). Следовательно, три делится только на 1 и на самого себя, а поэтому оно так же будет простым. Вычеркиваем из (1) все числа кратные 3, кроме самой тройки. Первое следующее за 3 не вычеркнутое число есть 5, оно не делится ни на 2, ни на 3 (иначе было бы вычеркнутым). Следовательно, 5 делится на 1 и на самого себя, а потому оно также будет простым и так далее.
Когда указанным способом уже вычеркнуты все числа кратные простых чисел меньших простого p, то все не вычеркнутые меньшие , будут простыми. Действительно, всякое составноенами уже вычеркнуто, как кратное его наименьшего простого делителя, который.
Отсюда следует:
1. Приступая к вычеркиванию кратных простого p, это вычеркивание следует начинать .
2. Составление таблицы простых чисел не превосходящих N закончено как только вычеркнуты все составные кратные простых, не превосходящих .
Пример (для самостоятельного решения).
Составить таблицу простых чисел не превосходящих N=60.
Единственность разложения на простые сомножители
Теорема.
Всякое целое a или взаимно просто с данным простым p, или же делится на p.
Доказательство.
(a, p) будучи делителем p может быть равно или 1 или p. В первом случае a взаимно просто с p, во втором a делится на p.
Теорема.
Если произведение нескольких сомножителей делится на простое p, то по крайней мере один из сомножителей делится на p.
Доказательство.
Каждый сомножитель или взаимно прост с p или же делится на p. Если бы все сомножители были взаимно просты с p, то их произведение было взаимно просто с p. Поэтому, хоть один сомножитель делится на p.
Теорема.
Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным образом (если отвлечься от порядка следования сомножителей).
Доказательство.
Пусть a – целое большее 1. Обозначив , его наименьший делитель имеем
. (1)
Если , то обозначив его наименьший простой делитель,
имеем
. (2)
Если , то аналогично получим
. (3)
и так далее, пока не придем к какому-либо . Тогда получим
. (n)
Перемножив (1), (2), (3),…,(n) и проведя сокращение получим следующее разложение на сомножители
. (A)
Допустим, что для a существует другое разложение
. (Б)
Тогда
. (В)
Правая часть равенства (В) делится на . Следовательно, по крайней мере, один из сомножителей левой части делится на. Пусть, напримерделится на(порядок следования сомножителей не играет роли). Тогда(кроме 1 делится только на). Сократив обе части равенства (В) на, получим
. (Г)
Применив преждние рассуждения к (Г), получим
. (Д)
и так далее пока, наконец, в одной части равенства, например, в левой не сократятся все сомножители. Но одновременно должны сократиться все сомножители левой части, так как равенство припревосходящих 1, невозможно.
Таким образом, второе разложение на простые сомножители тождественно первому.
studfiles.net
