欧拉函数线性筛

#include"iostream"
#include"vector"
#include"string.h"
using namespace std;
bool vis[10000];
int phi[10000];
vector<int>prime;
void PHI(int maxn)
{
    memset(vis,1,sizeof(vis));
    phi[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(vis[i])
        {
            prime.push_back(i);
            phi[i]=i-1;
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=maxn;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int main()
{
    PHI(50);
    for(int i=0;i<=50;i++)cout<<"i="<<i<<" "<<phi[i]<<"\n";
}
全部评论

相关推荐

Sigma429:极兔啊,薪资开的巨低,还在上海,索性不做笔试了
点赞 评论 收藏
分享
10-09 17:17
已编辑
门头沟学院 Java
活泼的代码渣渣在泡池...:同学你好,我也是学院本,后天要面这个亚信科技,是实习,请问问题都啥样呀,我项目就做了网上的,这是第一次面试
投递多益网络等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务