poj2478 Farey Sequence【筛法欧拉函数】

原题传送门

题意：

F2 = {1/2} 
F3 = {1/3, 1/2, 2/3} 
F4 = {1/4, 1/3, 1/2, 2/3, 3/4} 
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5} 
求出F(n) 有几个元素

也就是要你求    1~n   有几对   a与b   互质

这是一道欧拉函数的裸题

AC代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring> 
#define ll long long//筛法欧拉函数 
using namespace std;

const int maxn = 1000000 + 5;
int phi[maxn];

void init() {//打表，phi[n]，比n小，且与n互质的正整数个数
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for(int i = 2; i <= 1000000; i++){
		if(!phi[i]){
			for(int j = i; j <= 1000000; j += i){
				if(!phi[j]){
					phi[j] = j;
				}
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
}
int main() {
	int n;
	init(); 
	while(~scanf("%d", &n)){
		if(n == 0){
			break;
		}
		ll num = 0;
		for(int i = 2; i <= n; i++){
			num += phi[i];
		}
		printf("%lld\n",num);
	} 
	return 0;
}