前置知识:
1.试除法判断质数
2.各种筛质数算法
复杂度O(sqrt(n))
#include<iostream>
#include<unordered_map>
#include<assert.h>
#include<cmath>
using namespace std;
const int MAXN = 1e6;
int getRand(int min, int max) {
return ( rand() % (max - min + 1) ) + min ;
}
void decompose(int n){
int an = n;
unordered_map<int,int> primeFactor;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
while(n % i == 0){
primeFactor[i]++;
n /= i;
}
}
}
if( n > 1){
primeFactor[n]++;
}
int a = 1;
for(auto& [k,v] : primeFactor){
a *= pow(k,v);
}
assert( (a) == an);
}
int main(){
for(int i = 1; i <= MAXN; i++){
int a = getRand(2,2e9);
decompose(a);
}
return 0;
}