POJ 2478

找不能约分的分数，既找分子分母互质的分数


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define max 1000010
ll phi[max];
int n;
void getphi(){
	for(int i=0;i<max;i++)phi[i]=0;
	phi[1]=1;
	for(int i=2;i<max;i++){
		if(!phi[i]){
			for(int j=i;j<max;j+=i){
				if(!phi[j])phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
	}
}
int main(){
	getphi();
	//freopen("test.txt","r",stdin);
	while(cin>>n){
			if(n==0)break;
		ll sum=0;
		for(int i=2;i<=n;i++){
			sum+=phi[i];
		}
		cout<<sum<<endl;
	}
}

POJ 2478,布布扣,bubuko.com

POJ 2478

原文：http://www.cnblogs.com/Mr-Xu-JH/p/3863312.html