质因数个数
0质因数个数 - 蓝桥云课
质因数个数
问题描述
给定正整数 n，请问有多少个质数是 n 的约数。
输入格式
输入的第一行包含一个整数 n。
输出格式
输出一个整数，表示 n 的质数约数个数。
样例输入
396样例输出
3样例说明
396 有 2, 3, 11 三个质数约数。
评测用例规模与约定
- 对于 30% 的评测用例，1 ≤ n ≤ 10000。
- 对于 60% 的评测用例，1 ≤ n ≤ 10^9。
- 对于所有评测用例，1 ≤ n ≤ 10^16。
运行限制
- 最大运行时间：10s
- 最大运行内存：512M
思路：
首先我们要知道一个数n，他的质因子出现在2~sqrt(n)，或者n本身就是一个大于sqrt（n）,的质数。
假设n是某个大的质数的平方，那么当i循环到sqrt(n)的时候，如果n还没有被除尽，那么剩下的n可能就是一个大的质数。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e7+10;
ll n;
vector <ll> num;
int main(void)
{
map <ll,ll> mp;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(ll i = 2 ; i <= sqrt(n) ; i++)
{
ll k = i;
while(n % k == 0)
{
if(!mp[k])
{
mp[k] = 1;
num.push_back(k);
}
n /= k;
}
}
if(n > 1)
cout << num.size() + 1;
else
cout << num.size();
return 0;
}