int primes[N],cnt; //线性筛质数的primes数组和cnt
int phi[N]; //phi表示欧拉函数
bool st[N];
void get_eulers(int n)
{
/*1∼N 中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N)。*/
phi[1] = 1; //1与1互质
for(int i = 2; i <= n; i ++ )
{
if(!st[i])
{
primes[cnt ++] = i;
phi[i] = i - 1; //质数i与前面的i-1个数都与其互质
}
for(int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
//i % primes[j] == 0的情况
if(i % primes[j] == 0)
{
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
//i % primes[j] != 0的情况
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
}
【数学】线性筛法求欧拉函数
推荐阅读
- Alibaba高并发业务实战文档:互联网大厂100道Android面试题助你冲关金三银四!面试题+笔记+项目实战
- Android程序员:2021最新阿里Android面经,附高频面试题合集
- 安卓内存监控apk,这里有份超全Android体系化进阶学习图谱,安卓开发指南
- Android开发6年了,2021年大厂程序员进阶宝典,已拿offer附真题解析
- 42岁程序员面试,作为程序员一定不要仅仅追求物质!原理+实战+视频+源码
- 2021年安卓开发者跳槽指南,记录下我磕磕碰碰的三个月找工作经历,值得一读!
- Spring MVC 注解
- Lambda表达式树构建(上)
- Java中的异常处理
- 微信小程序之简单记账本开发记录(四)