题目 题目链接
题解 【#|[蓝桥杯][算法提高VIP]欧拉函数】筛素数 / 欧拉筛。
还有一个考点就是质因数，如何获取一个数的质因数？
遍历素数，若这个数能整除当前素数，就让这个数除这个素数直到不能整除为止，再遍历下一个素数，之后都是对除完的数进行相同的操作。
注意先除质因数后乘质因数-1，题目也说到了。
代码
#include
using namespace std;
const int N = 2000010;
int p[N], vis[N], prime[N];
int n, cnt;
int main()
{
for(int i = 2;
i <= N-10;
i ++) { // 欧拉筛
if(!vis[i]) prime[++cnt] = i;
for(int j = 1;
j <= cnt;
j ++) {
if(i*prime[j] > N-10) break;
vis[i*prime[j]] = 1;
if(i%prime[j] == 0) break;
}
}
while(cin>>n) {
int m = n, num = 0;
for(int i = 1;
i <= cnt;
i ++) {
if(prime[i] > m) break;
// 如果遍历到的质数都已经大于m了
if(m % prime[i] == 0) p[++num] = prime[i];
// 记录质因数
while(m % prime[i] == 0) m/=prime[i];
// 将m除到不再包含当前质因数
} for(int i = 1;
i <= num;
i ++)
n = n/p[i]*(p[i]-1);
// 先除后乘，题目说的太明确了，而且n除n的质因数是整除，所以不用担心 cout << n << endl;
} return 0;
} 推荐阅读
- #|HAL库_源码阅读
- #|SpringCloud Alibaba微服务中Nacos的服务注册与发现
- 刷题|【剑指 Offer】剑指 Offer 34. 二叉树中和为某一值的路径
- #|基于JAVA实现的WEB端UI自动化 -自动化测试简单介绍
- #|她笑了——心里阳光满满（Matlab实现一个太阳心）
- #|送小公主——哆啦A梦（Python代码实现）
- #|她很焦虑，是时候送一波更高级的玫瑰(Python&Matlab实现)
- #|你值得拥有——流星雨下的告白（Python实现）
- #|信息时代——微信防撤回（Python实现）