hdu1787 GCD Again poj 2478 Farey Sequence 欧拉函数

hdu1787，直接求欧拉函数

#include <iostream>

#include <cstdio>

using namespace std;

int n;

int phi(int n){

	int ans=n;

	for(int i=2; i*i<=n; i++)

		if(n%i==0){

			ans -= ans / i;

			while(n%i==0)	n /= i;

		}

	if(n>1)	ans -= ans / n;

	return ans;

}

int main(){

	while(scanf("%d", &n)!=EOF){

		if(!n)	break;

		printf("%d\n",n-phi(n)-1);

	}

	return 0;

}

poj2478，欧拉函数递推，证明可以看这里或者是算法竞赛进阶指南

\(n \log n\) 筛

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n;

long long phi[1000005];

void shai(){

	for(int i=2; i<=1000000; i++)

		phi[i] = i;

	for(int i=2; i<=1000000; i++)

		if(phi[i]==i)

			for(int j=i; j<=1000000; j+=i)

				phi[j] = phi[j] / i * (i - 1);

}

int main(){

	shai();

	for(int i=2; i<=1000000; i++)

		phi[i] += phi[i-1];

	while(scanf("%d", &n)!=EOF){

		if(!n)	break;

		printf("%lld\n", phi[n]);

	}

	return 0;

}

线性筛：

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, pri[1000005], cnt;

ll phi[1000005];

bool isp[1000005];

void shai(){

	memset(isp, true, sizeof(isp));

	isp[0] = isp[1] = false;

	for(int i=2; i<=1000000; i++){

		if(isp[i])	pri[++cnt] = i, phi[i] = i - 1;

		for(int j=1; j<=cnt; j++){

			if(i*pri[j]>1000000)	break;

			isp[i*pri[j]] = false;

			if(i%pri[j]==0){

				phi[i*pri[j]] = phi[i] * pri[j];//感性理解：12：1 5 7 11

				break;

			}

			else	phi[i*pri[j]] = phi[i] * (pri[j] - 1);//积性函数

		}

	}

}

int main(){

	shai();

	for(int i=2; i<=1000000; i++)

		phi[i] += phi[i-1];

	while(scanf("%d", &n)!=EOF){

		if(!n)	break;

		printf("%lld\n", phi[n]);

	}

	return 0;

}

上面那种得到了素数，下面这种得到了最小质因子

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, pri[1000005], cnt, val[1000005];

long long phi[1000005];

void shai(){

	for(int i=2; i<=1000000; i++){

		if(!val[i]){

			val[i] = i;

			pri[++cnt] = i;

			phi[i] = i - 1;

		}

		for(int j=1; j<=cnt; j++){

			if(pri[j]>val[i] || pri[j]>1000000/i)	break;

			val[i*pri[j]] = pri[j];

			phi[i*pri[j]] = phi[i]*(i%pri[j]?(pri[j]-1):pri[j]);

		}

	}

}

int main(){

	shai();

	for(int i=2; i<=1000000; i++)

		phi[i] += phi[i-1];

	while(scanf("%d", &n)!=EOF){

		if(!n)	break;

		printf("%lld\n", phi[n]);

	}

	return 0;

}