Арифметическая производная определена следующим образом:

• p' = 1 для любого простого числа p
• (ab)' = a'b + ab' для всех целых чисел a, b (правило Леибница).

Например, 20' = 24.

Найдите ∑ gcd(k,k') для 1 < k ≤ 5·10¹⁵.

Примечание: gcd(x,y) обозначает наибольший общий делитель (НОД) чисел x и y.