The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)
InputThere are several test cases. Each line has two integers a, b (2<a<b<3000000).OutputOutput the result of (a)+ (a+1)+....+ (b)Sample Input
3 100
Sample Output
3042
思路：欧拉函数前缀和板子
typedef long long LL;
const int maxm = 3e6+;
LL Euler[maxm];
void getEuler() {
Euler[] = ;
for(int i = ; i <= maxm; ++i) {
if(!Euler[i]) {
for(int j = i; j <= maxm; j += i) {
if(!Euler[j]) Euler[j] = j;
Euler[j] = Euler[j] / i * (i-);
}
}
}
}
int main() {
int a, b;
getEuler();
for(int i = ; i <= maxm; ++i)
Euler[i] += Euler[i-];
while(scanf("%d%d", &a, &b) != EOF) {
printf("%lld\n", Euler[b] - Euler[a-]);
}
return ;
}