Sum of Euler Totient
HardMathNumber Theory
Description
Return the sum of Euler's totient function phi(i) for i from 1 to n inclusive. phi(i) counts integers in [1, i] coprime to i.
Examples
Input:
n = 1Output:
1Explanation:
Phi(1) is defined as 1, so the sum equals 1.
Input:
n = 5Output:
10Explanation:
Phi values for 1..5 are 1, 1, 2, 2, 4 with a total sum of 10.
Input:
n = 10Output:
32Explanation:
Phi values for 1..10 are 1,1,2,2,4,2,6,4,6,4 and their sum is 32.
Constraints
- •
1 ≤ n ≤ 10⁵