Решето как метод решения задач. Введение

Наиболее известный метод построения объектов с помощью "решета" - это "решето Эратосфена" для построения множества простых чисел.
Про этот способ лучше всего спросить у "Иван Ивановича".
В теории чисел есть стандартные задачи:

1. найти делители числа (если их два, то число простое)
2. факторизовать число (то есть представить в виде степеней простых чисел)
3. определить количество делителей числа
4. определить  сумму делителей числа
5. определить является ли число "неквадратом", то есть не делиться на квадрат любого числа
6. и многое другое

Многие задачи могут быть интересны для всех чисел некоторого отрезка. 
Попробуем решить их используя "метод решета".
В качестве языка программирования рассмотрим Python и пока не будем задаваться вопросами эффективного кода.
Вопросы эффективного кода на Python и решения на C++ будут рассмотрены отдельно.
Здесь будем считать, что множество натуральных чисел ограничено 1_000_000 (и полезно добавть 0) 

Решето для определения множества простых чисел.
Напишем функцию для развертывания решета Эратосфена до N
Это базовая версия без попыток улучшения эффективности
 

def resheto_A(N):
    # создаем список для решета (последняя ячейка соответствует числу N -1 
    M = [1]*N
    # первове простое число 2, поэтому d = 2, а M[0]=0 и M[1] = 0
    d = 2 
    M[0] = M[1] = 0
    # просеивать/вычеркивать начинаем с d * d - в этом и состоит эффективность метода решета
    while d * d <= N :
        # вычеркиваем все кратные d начиная с d * d 
        for j in range( d * d, N, d): 
                M[j] = 0
        d += 1
    return M

Несколько задач, которые уже можно решить:

• количество простых чисел, не превосходящих N
• максимальное простое, меньшее N
• список простых чисел

Рассмотрим задачу, связанную с поиском делителей числа, но не для одного числа, а для всех чисел некоторого отрезка [A;B]
Задача:

• число с максимальным количеством делителей
• сумму всех делителей всех чисел отрезка
• количество чисел отрезка, для которых количество делителей больше 1% числа
• количество чисел отрезка, кратных количествуо делителей числа (числа Тау или рефенабельные числа)
• длину максимальной возрастающей последовательности количества делителей числа
• и т.п. (можете потренировать свою фантазию)

Модифицируем решето Эратосфена по данную задачу

• заполним список 1 (так как 1 - делитель любого числа)
• начиная с d с шагом d будем заносить по +1 в каждую ячейку

Эффективности не будет, но можно делать это для чисел от A до В 
(как это сделать обсудим отдельно, а здесь рассмотрим отрезок от 1 до 1_000_000)  

 
def resh_k_del(N):
    # создаем список для решета (последняя ячейка соответствует числу N)  все числа делятся на 1, поэтому по умолчанию 1
    M =[0] + [1]*N
    # первове простое число 2, поэтому d = 2, 
    d = 2 
    # будем добавлять по 1 начиная с d 
    while d  <= N :
        # добавлеям по 1 ко всем кратным d начиная с d 
        for j in range( d , N+1, d): 
                #увеличиваем количество делителей на 1
                M[j] += 1 
        d += 1
    return M
 
 

Рассмотрим ещё одну задачу на делители, связанную с суммой делителей числа]
Задача:
Для всех чисел отрезка [A;B] найдите сумму делителей этого числа.
Определите значения:

• число с максимальной суммой делителей
• все совершенные числа (сумма делителей равна удвоенному числу)
• все мультисовершенные числа (сумма делителей кратна число)
• длину максимальной возрастающей последовательности суммы делителей числа
• и т.п. (можете потренировать свою фантазию)

Модифицируем решето Эратосфена по данную задачу

• заполним список 1 (так как 1 - делитель любого числа)
• начиная с d с шагом d будем заносить по +d в каждую ячейку

Эффективности не будет, но можно делать это для чисел от A до В 
(как это сделать обсудим отдельно, а здесь рассмотрим отрезок от 1 до 1_000_000)  

def resh_sum_del(N):
    # создаем список для решета (последняя ячейка соответствует числу N)  все числа делятся на 1, поэтому по умолчанию 1
    M =[0] + [1]*N
    # первове простое число 2, поэтому d = 2,
    d = 2 
    # перебирам начинаем с d 
    while d  <= N :
        # добавляем ко всем кратным d начиная с d по  +d 
        for j in range( d , N+1, d): 
                #увеличиваем сумму делителей на d
                M[j] += d 
        d += 1
    return M

Рассмотрим задачу о числе "неквадратов" для всех чисел отрезка
(число называется "неквадратом", если оно не кратно квадрату любого простого числа)
Задача:
Для всех чисел отрезка [A;B] определите, является ли оно  "неквадратом"
Определите значения:

• количество "неквадратов" на отрезке
• максимальное расстояние между "неквадратами"
• и т.п. (можете потренировать свою фантазию)

Модифицируем решето Эратосфена по данную задачу

• заполним значением от 1 список размера N
• начиная с d * d в с шагом d * d будем заносить в список 0

Эффективности  будет очень большой и можно развертывать решето для больших N 
 

def resh_k_del(N):
    # создаем список для решета (последняя ячейка соответствует числу N)  все числа делятся на 1, поэтому по умолчанию 1
    M =[0] + [1]*N
    # первове простое число 2, поэтому d = 2, 
    d = 2 
    # будем добавлять по 1 начиная с d 
    while d  <= N :
        # добавлеям по 1 ко всем кратным d начиная с d 
        for j in range( d , N, d): 
                #увеличиваем количество делителей на 1
                M[j] += 1 
        d += 1
    return M