B3871 [GESP202309 五级] 因数分解

B3871 [GESP202309 五级] 因数分解

感觉像是一个欧拉筛的模板题吧。
首先先用欧拉筛把10的6次方之内的素数都打出来，然后对于给定的n，遍历每一个素数。如果出现是素数的倍数的话，就先除掉这个素数，并且让计数加一。
最后如果出来发现剩下的并不等于1的话，说明没有除尽，那么这个没有除尽的一定是一个剩下的大素数。
（因为数据范围已经给在这里了，不存在剩下的是两个大素数相乘。如果是的话，肯定会超过10的12次方）

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e6+100;
int vis[N],prim[N],cnt = 0;
int n;
void init()
{int num = 1e6;for(int i = 2 ; i <= num ; ++i)   {if(!vis[i])prim[++cnt] = i;for(int j = 1 ; 1ll * i * prim[j] <= num ; ++j){vis[i*prim[j]] = 1;if(i % prim[j] == 0)break;}}
}
signed main()
{cin>>n;int flag = 0;init();for(int i = 1 ; i <= cnt ; ++i){int sum = 0;while(n % prim[i] == 0){n/=prim[i];sum++;if(n == 1)break;}if(sum == 0)continue;if(flag)cout<<" * ";if(sum == 1)cout<<prim[i];elsecout<<prim[i]<<"^"<<sum;flag = 1;sum = 0;if(n == 1)break;}if(n != 1){if(flag)cout<<" * ";cout<<n;}return 0;
}