ABC300D查找符合要求的两个质因子

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
long long n, m, i, j, k, a, b, c, s, f[N], p[N];
int main(){
    scanf("%lld", &m);
    for(i=2; i<N; i++){
        if(!f[i]) p[++n] = i, f[n] = i*i;//存储c*c
        for(j=i+i; j<N; j+=i){
            f[j] = 1;
        }//筛法
    }
    for(i=1; (a=p[i])&&a<1000; i++){//5次方在m以内
        for(j=i+1; b=p[j]; j++){//a*a*b*c*c <= m
            k = upper_bound(f+1, f+n+1, m/(a*a*b))-f;//第1个不符合要求的
            while(a*a*b*f[k] > m) k--;//往回退几个即可
            if(k > j) s += k - j;
            else break;
        }
    }
    printf("%lld\n", s);
    return 0;
}