Project Euler Problem 484
The arithmetic derivative is defined by - p^prime = 1 for any prime p - (ab)^prime = a^prime b + ab^prime for all intege
Solution
Answer: 8907904768686152599
Using the multiplicative characterization of
$$g(n)=\gcd(n,n')$$
one can show that if
$$n=\prod p_i^{e_i},$$
then
$$g(n)=\prod p_i^{,e_i-1+\mathbf 1_{p_i\mid e_i}},$$
because
$$n' = n\sum_i \frac{e_i}{p_i},$$
and for each prime $p_i$, the $p_i$-adic valuation of $n'$ is exactly $e_i-1$, with one extra factor of $p_i$ iff $p_i\mid e_i$. This makes $g(n)$ a multiplicative function and enables a powerful-number / Möbius-prefix summation in roughly $O(\sqrt N)$ time for $N=5\times 10^{15}$.
The exact Project Euler value is:
Answer: 8907904768686152599