#P6805. *【莫比乌斯反演:杜教筛】 欧拉函数求和

*【莫比乌斯反演:杜教筛】 欧拉函数求和

题目描述

给定一个正整数 nn ,求:i=1nφ(i)\sum\limits_{i=1}^n\varphi(i)

输入格式

一个整数 n (1n<231)n \ (1 \leq n \lt 2^{31})

输出格式

输出一行一个整数,代表 i=1nφ(i)\sum\limits_{i=1}^n\varphi(i)

10
32