题解 | #质因数的个数#

质因数的个数

https://www.nowcoder.com/practice/20426b85f7fc4ba8b0844cc04807fbd9

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector<int> getzys(int N) {
//筛选出小于等于根号n的所有素数,大于根号n的素数最多只有一个,不需要知道是什么,只需要判断除以全部小于等于根号n的质因子后是否还大于1
    int MAX = sqrt(1e9) + 1;
    bool nums[MAX];
    vector<int> ans;
    for (int i = 0; i < MAX; i++) {
        nums[i] = true;
    }
    nums[0] = nums[1] = false;
    for (int i = 2; i < MAX; i++) {
        if (!nums[i]) continue;
        ans.push_back(i);//保存素数
        for (int j = i * i; j < MAX; j += i) {
            nums[j] = false;
        }
    }
    return ans;
}

int main() {
    int n;
    vector<int> zys = getzys(n);
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        int count = 0;
        int bound = sqrt(n);//大于根号n的质因数最多只有一个
        for (int i = 0; i < zys.size()&&zys[i]<=bound ; i++) {
            int temp = zys[i];
            while (n % temp == 0) {
                count++;
                n /= temp;
            }
        }
        if (n > 1) count++;
        cout << count << endl;
    }
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

昨天 11:10
武汉纺织大学 C++
点赞 评论 收藏
分享
26牛牛不会梦到感谢信:羡慕离职了还能吃吗现在就赶回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务