质因数的个数

预处理每个数的最小质因数，再递推计算每个数的质因数个数，最后在区间 [N, M] 内找出最大值。

#include <bits/stdc++.h>
using namespace std;
int p[10000001];  //最小质因数
int c[10000001];  //质因数个数
void get(int b) {
    for(int i=0; i<=b; i++) {
        p[i] = i;
    }
    for(int i=2; i*i<=b; i++) {
        if(p[i] == i) { // i是质数
            for(int j=i*i; j<=b; j+=i) {
                if(p[j] == j) { // j未被更小质因数标记
                    p[j] = i;
                }
            }
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b;get(b);
    // 递推计算质因数个数
    for(int i=2; i<=b; i++) {
        if(p[i] == i) {
            c[i] = 1; 
        } else {
            c[i] = c[i/p[i]] + 1; 
        }
    }
    // 找区间[a,b]内的最大值
    int m = 0;
    for(int i=a; i<=b; i++) {
        m=max(m,c[i]);
    }
    cout << m;
    return 0;
}

时间复杂度：O(bloglogb)
空间复杂度：O(b)