分解质因数
2024-10-26 16:59:12
发布于：广东
17阅读
0回复
0点赞
能过 的数据
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#define int long long
using namespace std;
vector <pair <int, int>> v;
bitset <10000005> vis;
signed main(){
int n;
cin >> n;
cout << n << '=';
for(int i = 2; i * i <= n; i++){//线性筛加速
if(!vis[i]) v.push_back({i, 0});
for(auto j:v){
if(i * j.first * i * j.first > n) break;
vis[i * j.first] = 1;
if(!(i % j.first)) break;
}
}
for(auto &i:v){//记录质因数
while(n % i.first == 0){
i.second++, n /= i.first;
}
}
bool flag = 0;
for(auto i:v){
if(i.second){//输出
if(flag) cout << '*';
else flag = 1;
cout << i.first;
if(i.second >= 2) cout << '^' << i.second;
}
}
if(n != 1){
if(flag) cout << '*';
cout << n;
}
}
有帮助，赞一个