プロジェクトオイラー問70 - sinapusu2002 @ ウィキ

Problem 70 「トーティエント関数の置換」 †
オイラーのトーティエント関数 φ(n)に関する問題。

定義域全部のファイ値を計算しても最近のパソコンなら何の問題もないですね
2.8秒これは遅いのか早いのか微妙な速度。
どちらかというと遅い。

#include<stdio.h>

const int LIMIT=1000*10000;
int fai[LIMIT];



int main(){
	for(int i=2;i<LIMIT;i++){
		fai[i]=i;
	}
	for(int i=2;i<LIMIT;i+=1+(i&1)){
		if(fai[i]!=i)continue;
		for(int j=i;j<LIMIT;j+=i){
			fai[j]=(fai[j]/i)*(i-1);
		}
	}
	int ans=-1;
	double ansD;
	for(int i=2;i<LIMIT;i++){
		int count[10]={0};
		int e2=fai[i];
		int e1=i;
		while(e1>0){
			count[e1%10]++;
			e1/=10;
 		}
	while(e2>0){
 			count[e2%10]--;
			e2/=10;
		}
		int out=0;
		for(int j=0;j<10;j++)out+=(count[j]!=0);
		if(out==0){
			double d=1.0*i/fai[i];
 			if(ans==-1||ansD>d){
				ans=i;
				ansD=d;
			}
		}
	}
	printf("%d\n",ans);
}