Интернет магазин китайских планшетных компьютеров

Компьютеры - Решето Эратосфена - Решето Эйлера

Решето Эйлера это вариант решета Эратосфена в котором каждое составное число удаляется из списка только один раз.

Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, и определяются его произведения на каждое число в списке которые маркируются для последуюшего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:

 5  7  9 11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
    7    11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
         11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
            13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, перед k-ым этапом рабочий список содержит только числа взаимно простые с первыми простыми числами простых чисел), и начинается с k-го простого числа. Все числа в списке, до квадрата его первого числа, являются простыми.