Формула включений-исключений

, то есть нас интересуют числа, деляющиеся на или Найдём сначала количество таких чисел. Для этого воспользуемся принципом включений и исключений. Чётных чисел от до ровно , кратных трём — , кратных пяти — . Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа, делящиеся на и , поэтому из полученной суммы надо вычесть и . Однако, всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа. Количество таких чисел , значит, количество чисел, имеющих с общие делители и не превосходящих его, это

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

Замечание.

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