欧拉筛: 时间复杂度:
#include <stdio.h>
#define MAX 65535
int Prime(int,int*,int*,int*);
int main(void)
{
int prime[MAX]={0};
int check[MAX]={0};
int phi[MAX]={0};//欧拉函数
printf("%d",Prime(1000,prime,check,phi));
return 0;
}
int Prime(int max,int* prime,int* check,int* phi)
{
int j=0;
for(int i=2;i<=max;i++)
{
if(check[i]==0)
{
prime[j]=i;
j++;
phi[i]=i-1;
}
for(int k=0;i*prime[k]<=max;k++)
{
int l=i*prime[k];
check[i*prime[k]]=1;
if(i%prime[k]==0)
{
phi[l]=phi[i]*prime[k];
break;
}
else
phi[l]=phi[i]*(prime[k]-1);
}
}
return j;
}
维基百科:欧拉函数
http://blog.csdn.net/nk_test/article/details/46242401