题意:一个自然数最多可以分解成多少个不同的因子。
思路:
枚举题,主要在暴力的基础上减去不必要的枚举。
1.因为n(1除外)一定存在一个小于的因子,所以枚举到因子枚举到就可以了。
2.每找到一个因子就从n分离出来:
3.当时,有两个一样的未出现的因子,那么只能把这两个因子合并为算作一个因子。
4.当时,(假设x是上一个分解的因子)表示没有比x还大的因子对了,就是比如,需要a和b都大于x,不然分解出b后分解a时一定会重,因为a小于分解出来的一些因子,说明a的因子包括a,前面已经出现过了。
5.所以如果,把他算作一个因子,不能再分解了。
Code:
#include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; int main() { js; int t,n; cin>>t; while(t--) { int ans=0; cin>>n; for(int i=1;i*i<n;++i) { if(n%i==0) { ++ans; n/=i; } } cout<<ans+1<<endl; } }