思路:试除法
- 算术基本定理(唯一分解定理)
每个正整数都能唯一的表示成它的质因数的乘积
比如 $280=2^3*5^1*7^1$ - N 中最多只含有一个大于 $\sqrt n$ 的质因子
- 分解质因数
在 2~$\sqrt n$ 的范围枚举,如果遇到质因子就除净并且记录质因子的个数。
最后如果 $n>1$ ,说明这就是那个大于 $\sqrt n$ 的质因子
代码
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
ll n,res=0;
cin>>n;
//2~根号n的范围内枚举
for(int i=2;i<=n/i;i++){
if(n%i==0){
res++;
//除净
while(n%i==0) n/=i;
}
}
//大于根号n的质因数
if(n>1) res++;
cout<<res;
return 0;
}