POJ2478 Farey Sequence 欧拉函数与素数 数论题

这题主要是求1..n-1中与n互质的数的个数，并且要将其累加起来

我写的代码套用了求欧拉数的函数，结果超时，求大牛点拨优化方法

#include <iostream>
#include <cstdio>
using namespace std;
int eun[1000005] = {0};
//求1..n-1中与n互质的数的个数
int eular(int n){
	int ret=1,i;
	for (i=2;i*i<=n;i++)
		if (n%i==0){
			n/=i,ret*=i-1;
			while (n%i==0)
				n/=i,ret*=i;
		}
		if (n>1)
			ret*=n-1;
		return ret;
}
int main(){
	int n,i,sum;
	for (i = 2;i <= 1000000 ;i++)
	{
		eun[i] = eular(i);
	}
	while (1)
	{
		//cin>>n;
		scanf("%d",&n);
		if (n == 0)
			break;
		sum = 0;
		for (i = 2;i <= n ;i++)
		{
			sum += eun[i];
		}
		//cout<<sum<<endl;
		printf("%d",sum);
	}
	return 0;
}

在网上看到网友的解答，摘录余下：

#include <stdio.h>
#include <string.h>
#include <math.h>
const int maxn = 1000000+1;
//const int maxn = 1000+5;
double save[maxn];
void init()
{
	int i,j;
	for (i = 2; i < maxn; i ++)
		save[i] = i;
	for (i = 2; i < maxn; i ++)
	{
		if(save[i] == i)
		{
			save[i] = i-1;
			for(j=2*i;j<maxn;j+=i)
				save[j]=save[j]*(1-(double)1/(double)i);
		}
	}
	for (i = 2; i < maxn; i ++)
		save[i] += save[i-1];
}
int main()
{
	int n;	
	
	init();
	while (scanf("%d",&n),n != 0)
	{
		printf("%.0lf/n",save[n]);
		
	}
	return 0;
}