根号级质数判断及质因数分解
bmatrix
·
·
个人记录
```cpp
bool is_prime(int x){
if(x<2)return 0;
for(int i=2;i*i<=x;i++)
if(x%i==0)return 0;
return 1;
}
```
$\Omega(\log n)\quad O(\sqrt n)$ 质因数分解：
```cpp
//如果对质因数的顺序有要求可以改成std::map
std::unordered_map<int,int> prime_factors(int x){
std::unordered_map<int,int>fct;
if(x<2)return fct;
int i=2;
while(i*i<=x){
while(x%i==0)x/=i,fct[i]++;
i++;
}
if(x!=1)fct[x]++;
return fct;
}
```
我相信各位大佬都会这东西，只是我太菜了