Нахождение пар кратных чисел. Эффективный алгоритм.

Необходимо найти количество пар, произведение чисел которых кратно 34.

Число 34 можно разложить на 2 простых: 17 и 2.

Нужно подсчитать количество чисел по кратности при вводе:

Формула для нахождения чисел, кратных 34:

k(k-1)/2+k(N-k)+k2*k17,

где k(k-1)/2 - количество пар, где оба сомножителя делятся на 34,
k(N-k) - количество пар, где только один сомножитель делятся на 34,
k2*k17 - количество пар, которые не делятся на 34, но один сомножитель делится на 17, другой на 2.
Формула для нахождения чисел, НЕ кратных 34:

N(N-1)/2-(k(k-1)/2+k(N-k)+k2*k17),

где N(N-1)/2 - общее количество возможных пар.