看破欧拉函数的奥秘

注意以下三个特殊性质

编程实现   利用欧拉函数和它本身不同质因数的关系,用筛法计算出某个范围内所有数的欧拉函数值。

 1 //直接求解欧拉函数  
 2 #include<cstdio>
 3 int euler(int n){ //返回euler(n)   
 4     int res=n,a=n;  
 5     for(int i=2;i*i<=a;i++){//从小到大尝试n的质因数 
 6         if(a%i==0){//如果i是n的质因数 
 7             res=res/i*(i-1);//提了一个1/i出来,先进行除法是为了防止中间数据的溢出   
 8             while(a%i==0) a/=i;//欧拉函数只记算一种质因数 
 9         }  
10     }  
11     if(a>1) res=res/a*(a-1);//如果最后还剩因子 
12     return res;  
13 }
14 int main(){
15     int x;
16     scanf("%d",&x);
17     printf("%d",euler(x));
18     return 0;
19 }
 1 //筛选法打欧拉函数表   
 2 #include<cstdio>
 3 #define Max 1000001  
 4 int euler[Max];  
 5 void Init(){
 6     euler[1]=1;
 7     for(int i=2;i<Max;i++)
 8         euler[i]=i;
 9     for(int i=2;i<Max;i++)
10         if(euler[i]==i)//如果i是质数 
11             for(int j=i;j<Max;j+=i) 
12                 euler[j]=euler[j]/i*(i-1);//提一个1/i,先进行除法是为了防止中间数据的溢出
13     return ;
14 }
15 int main()
16 {
17     Init();
18     for(int i=1;i<=100;i++)
19         printf("%d\n",euler[i]);
20     return 0;
21 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

09:LGTB 学分块

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB描述 LGTB 最近在学分块,但是他太菜了,分的块数量太多他就混乱...

3497
来自专栏编程

看不懂CNC编程?送你一份CNC程序代码大全

一、常用地址符含义 二、数控FANUC加工中心编程指令代码详解 辅助功能M指令 注:在一个程序段中只能有指令一个M指令,如果在一个程序中出现两个或两个以上的M指...

3270
来自专栏云霄雨霁

数据结构----符号表

1670
来自专栏HansBug's Lab

1819: [JSOI]Word Query电子字典

1819: [JSOI]Word Query电子字典 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 729  ...

3504
来自专栏深度学习那些事儿

探讨pytorch中nn.Module与nn.autograd.Function的backward()函数

本文讲解基于pytorch0.4.0版本,如不清楚版本信息请看这里。backward()在pytorch中是一个经常出现的函数,我们一般会在更新loss的时候使...

1.6K5
来自专栏xingoo, 一个梦想做发明家的程序员

Sqoop切分数据的思想概况

Sqoop通过--split-by指定切分的字段,--m设置mapper的数量。通过这两个参数分解生成m个where子句,进行分段查询。因此sqoop的spl...

1925
来自专栏温安适的blog

贪婪算法-单源最短路径

3765
来自专栏锦小年的博客

python学习笔记6.7-简化数据结构的初始化过程

我们每编写一个类的时候都需要编写一个初始化函数,那么如果编写的类当做数据结构来用,它们的初始化结构就是一样的,例如: class Stock: def ...

2156
来自专栏安恒网络空间安全讲武堂

hacklu CTF 2018 Baby PHP

过file_get_contents()用到了php伪协议。https://www.lorexxar.cn/2016/09/14/php-wei/。只要通过ph...

2262
来自专栏HansBug's Lab

1293: [SCOI2009]生日礼物

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1096  Solv...

2727

扫码关注云+社区

领取腾讯云代金券