простые-числа - Falcao выручайте! 1940 , непростые годы.

Основой применяемого алгоритма является формула включений и исключений из комбинаторики. Когда берутся все натуральные числа от 1 до 100, то мы хотим узнать, какое их количество не делится ни на одно из простых чисел списка 2, 3, 5, 7 (это частный пример, но на нём всё можно понять). Достаточно легко подсчитать, сколько чисел от 1 до 100 делится на 2. Ясно, что их будет 50. Делящихся на 3 чисел будет 33: это целая часть отношения 100/3. Вообще, для любого натурального $%m$%, будь то 2, 3, 6, 15 или какое угодно число, на $%m$% будут делиться ровно $%[n/m]$% чисел.

Обозначим через $%A_m$% множество тех чисел от 1 до 100, которые кратны $%m$%. Нас здесь интересует число элементов объединения $%|A_2\cup A_3\cup A_5\cup A_7|$%. Согласно формуле включений и исключений, это будет следующая величина: $%|A_2|+|A_3|+|A_5|+|A_7|-|A_2A_3|-|A_2A_5|-|A_2A_7|-|A_3A_5|-|A_3A_7|-|A_5A_7|$%+$%|A_2A_3A_5|+|A_2A_3A_7|+|A_2A_5A_7|+|A_3A_5A_7|-|A_2A_3A_5A_7|$%. Это число элементов в каждом из множеств, минус число элементов в каждом из попарных пересечений, плюс число элементов в каждом из тройных пересечений, минус число элементов в пересечении четырёх множеств, и так далее. Заметим, что $%|A_2A_3|=|A_6|=[\frac{100}6]$%, и аналогично для остальных случаев. И если теперь мы хотим подсчитать, сколько чисел от 1 до $%n=100$% не будут делиться ни на 2, ни на 3, ни на 5, ни на 7, то из общего количества надо будет вычесть то, что получилось выше. Итогом будет $%n-[\frac{n}2]-[\frac{n}3]-[\frac{n}5]-[\frac{n}7]+[\frac{n}{2\cdot3}]+[\frac{n}{2\cdot5}]+[\frac{n}{2\cdot7}]+[\frac{n}{3\cdot5}]+[\frac{n}{3\cdot7}]+[\frac{n}{5\cdot7}]-$% $%[\frac{n}{2\cdot3\cdot5}]-[\frac{n}{2\cdot3\cdot7}]-[\frac{n}{2\cdot5\cdot7}]-[\frac{n}{3\cdot5\cdot7}]+[\frac{n}{2\cdot3\cdot5\cdot7}]$%. Это и есть те прибавления/вычитания, которые используются в ходе алгоритма. Знак "плюс" или "минус" определяется тем, сколько сомножителей у выражения имеется в знаменателе (чётное или нечётное количество, соответственно).