首页 > 代码库 > 学习欧拉phi函数的思考

学习欧拉phi函数的思考

其正确性思考写在了代码片上


忘记一件事:欧拉phi函数的作用是用来求1~n中与n互素的数的个数微笑

#include<cstdio>
#include<cstring>
#include<cmath>

int phi[5000000];


///考虑到若所计算的数字是6,当i=2和i=3时都将会进入内层循环,
///一旦进入内层循环就会在该素数的基础上进行欧拉公式的运算
///插入:欧拉公式:phi(n)=n*(1-1/p1)*(1-1/p2)*...(1-1/pn)
///可以想到对于每一个确定的数字n来说,其欧拉公式的运算并不在一次循环中完成,
///但可以证明的一点是,当整个循环完成时,其欧拉公式的运算会完成,换句话说,是能够保证
///phi(n)这个数组中是严格按照欧拉公式算得的正确答案,而非按照其他算法
void phi_table(int n,int* phi)
{
    for(int i=2;i<=n;i++)
    {
        phi[i]=0;
    }
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!phi[i])
        {
            for(int j=i;j<=n;j+=i)
            {
                if(!phi[j]) phi[j]=j;
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
}
int main()
{

    phi_table(10000,phi);
    int n;
    while(scanf("%d",&n))
        printf("%d\n",phi[n]);
}

上述代码中打印欧拉函数值的代码是正确的,但整份代码是为了验证和证明欧拉phi函数,并没有其他用意