AcWing 4658. 质因数个数

链接 :?

https://www.acwing.com/problem/content/4661/

思路 :?

质因数分解

算法过程：
从2开始枚举所有的因数，到n / i
如果n % I == 0, 使用while循环将该质数除尽，并累加数量
如果最后n > 1，输出这个唯一一个大于√n的质因子。

首先给出y总的质因数分解的模板 :

void divide(int x)
{
? ? for (int i = 2; i <= x / i; i ++ )
? ? ? ? if (x % i == 0){
? ? ? ? ? ? int s = 0;
? ? ? ? ? ? while (x % i == 0) x /= i, s ++ ;
? ? ? ? ? ? cout << i << ' ' << s << endl;
? ? ? ? }
? ? if (x > 1) cout << x << ' ' << 1 << endl;
? ? cout << endl;
}

然后按照模板，统计一下个数(这里直接用set.size()表示)就行了，详细请看代码 :

代码 :?

#include<bits/stdc++.h>
using namespace std;
typedef long long LL ;

LL x ; 

int main(){
    cin >> x ;
    set<LL> st ;
    LL ans = 0 ;
    for(LL i=2;i<=x/i;i++){
        if(x%i==0){
            while(x%i==0) x/=i;
            ans ++ ;
        }
    }
    if(x>1) ans ++;
    cout << ans << endl ;
}