Poj2478

线性素数筛求欧拉函数，再求欧拉函数的和

#include <iostream>

#include <stdio.h>

using namespace std;

 

const int MAX=1000000;

 

long long sum[MAX+10];

bool prime[MAX+10];

long long phi[MAX+10];

void getprime()

{

int i,j;

prime[0]=prime[1]=0;

for(i=2;i<=MAX;i++)

prime[i]=1;

for(i=2;i*i<=MAX;i++)

if(prime[i])

for(j=i*i;j<=MAX;j+=i)

prime[j]=0;

}

void eu()

{

int i,j;

for(i=1;i<=MAX;i++)

phi[i]=i;

for(i=2;i<=MAX;i++)

{

if(prime[i])

for(j=i;j<=MAX;j+=i)

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

}

}

 

int main()

{

int n;

getprime();

eu();

sum[2]=1;

for(int i=3;i<=MAX;i++)

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

freopen("in.txt","r",stdin);

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

{

if(n==0)

break;

else

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

}

return 0;

}