Треба порахувати, скільки чисел від до діляться на або на . Це класичне застосування формули включень-виключень.
Кратних до у відрізку рівно , кратних до — . Якщо просто додати ці дві величини, то числа, кратні обом одразу, буде враховано двічі, тому їх треба відняти один раз.
Число ділиться і на , і на тоді й лише тоді, коли воно ділиться на їхнє найменше спільне кратне
Отже, відповідь дорівнює
Дуже поширена помилка — узяти замість НСК просто добуток A \cdot B. Це правильно лише коли і взаємно прості; наприклад, для A = 2, B = 4 добуток дав би замість правильного НСК .
Друга пастка — переповнення: обчислюйте НСК як A / \gcd(A,B) \cdot B (спочатку ділення, потім множення), щоб проміжний добуток не вискочив за межі типу.
Найбільший спільний дільник знаходиться алгоритмом Евкліда за .