王道机试指南 例题6.9 质因数的个数

题目：

算法：

重要结论：

代码：

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

bool IsSushu(int x){//判断x是否为素数
    if(x<2) return false;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0) return false;
    }
    return true;
}

vector<int> Sushu(int x){//返回由所有小于x的素数构成的数组
    vector<int> res;
    for(int i=2;i<x;i++){
        if(IsSushu(i)==1) res.push_back(i);
    }
    return res;
}

int main() {
    int n;
    while(cin>>n){
        vector<int> arr=Sushu(sqrt(n)+1);//素数只需筛到sqrt(n)
        int count=0;//记录质因数个数
        int i=0;
        while(n!=1 && i<arr.size()){
            if(n%arr[i]==0){
                n=n/arr[i];
                count++;
            }
            else{
                i++;
            }
        }
        if(n!=1) count++;//如果n!=1，则必定存在且仅存在一个大于sqrt(n)的质因数
        cout<<count<<endl;
    }
    return 0;
}

运行结果：