数论笔记:欧拉筛法与欧拉函数

欧拉筛: 时间复杂度:

#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