用筛法直接记录最大质因子

#include<iostream>
using namespace std;
int max_p[1000001];  // max_p[i]表示i的最大质因子
int main()
{
    int n,B,s=1;  // 1算作B-smooth
    cin>>n>>B;
    
    // 筛法：对每个质数p，标记p的所有倍数的最大质因子为p
    for(int i=2;i<=n;i++)
    {
        if(max_p[i]==0)  // i是质数
        {
            for(int j=i;j<=n;j+=i)
                max_p[j] = i;  // j的最大质因子至少是i
        }
    }
    
    // 统计最大质因子不超过B的数的个数
    for(int i=2;i<=n;i++)
    {
        if(max_p[i] <= B)
            s++;
    }
    
    cout<<s;
	return 0;
}