[蓝桥杯][算法提高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) {
		int m = n, num = 0;
		for(int i = 1;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