C++实现求n到m之间数的质约数个数

实现一：

#include<iostream>
using namespace std;

int cf(int, int);
bool js(int);

int main()
{
    int n, m;
    cin >> n >> m;

    if(n > m){
        cout << "输入不合法，第一个数字要小于等于第二个数字" << n << m << endl;
        return 0;
    }
    //定义最大个数
    int max = 0;
    for(int i = n; i <= m; i++){
        /*if(i == m){
            cout << m << endl;
        }*/
        //如果是质数，只有1和本身
        bool isjs = js(i);
        if(isjs){
            continue;
        }
        int total = cf(i, 0);
        //如果当前的total > max，则把max值替换
        if(total > max){
            max = total;
        }
    }
    cout << max << endl;
    return 0;
}

int cf(int i, int total)
{
    for(int j = 2; j <= i; j++){
        while (i % j == 0)    //若j为i的质因数，则输出i
        {
            i /= j;    //对i除以j后的数求取质因数
            total ++;
        }
    }

    return total;
}

bool js(int i)
{
    //假设这个数字为质数
    bool isJs = true;
    //除了1和它本身，则循环从2开始并且小于它本身
    for(int j = 2; j < sqrt(i); j++){
        //能被任意一个数整队，所以不是素数
        if(i % j == 0){
            isJs = false;
            break;
        }
    }
    return isJs;
}

实现二（优化）：

#include <iostream>
#include <cmath>
using namespace std;
const int MAX_SIZE = 10000001; //定义最大长度，10的7次方
int zsgs[MAX_SIZE]; // 质数个数
int zssl[MAX_SIZE]; // 质数列表
bool zs[MAX_SIZE];  // 是否为质数
int nCount = 0;     //

int main()
{
    int a, b;
    cin >> a >> b;
    if(a > b){
        cout << "输入不合法，第一个数字要小于等于第二个数字" << a << b << endl;
        return 0;
    }
    int best = 1;
    for (int i = 2; i <= b; i++)
    { 
        // 从2开始遍历
        if (zs[i] == false)
        {
            zssl[++nCount] = i;
            zsgs[i] = 1;
        }
        // 从低往高遍历，所以低位肯定是质数
        for (int j = 1; j <= nCount && zssl[j] * i <= b; j++)
        {
            // 得到质数后，往上相乘，得到的数必定是合数
            // 根据规律：合数可以拆分为一个质数和另一个数，质因子数量为另外一个数的质因子数量+1(质数的质因子数量为1)
            // 举例：8 = 2 * 2 * 2，质因数个数为3
            // 8 = 2 * 4，质因数个数为2的质因数个数(1)+4的质因数个数(2)=3个
            // 4 = 2 * 2，因数个数为2的质因数个数(1) + 因数个数为2的质因数个数(1))=2个
            int num = i * zssl[j];
            zs[num] = true;
            zsgs[num] = zsgs[i] + 1;
            if (num >= a)
            {
                best = max(best, zsgs[num]); // 求出最值
            }
        }
    }
    cout << best;
    return 0;
}