【题目大意】给定n和B，求解有多少个<=n的最大质因子不超过B的B-smooth数

【考纲知识点】唯一分解定理

【解题思路】

①比较朴素的思路为循环遍历1~n,对于每个i，对其分解质因子，得到最大质因子，将质因子和B作比较，并统计到答案中，该算法循环复杂度为O(n),调用分解质因子的复杂度为O(sqrt(n))，总体复杂度为O(nsqrt(n)),加上需要初始化等常数操作，通过1e6的数据是比较危险的。

②考虑在筛法求素数时,对素数P，其倍数都包含素因子P,可以在筛掉素因子P的倍数的同时，用P更新这些倍数的最大素因子。埃式筛法没问题，当然也可以选择欧拉线性筛进一步将复杂度降低为线性。

【参考程序】

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n, B;
  cin >> n >> B;
  assert(1 <= n && n <= 1e6);
  assert(1 <= B && B <= 1e6);
  vector<bool> vis = vector<bool>(n + 5, false);
  vector<int> mx_prime_factor = vector<int>(n + 5, 0);
  vector<int> prime;
  mx_prime_factor[1] = 1;
  for (int i = 2; i <= n; i++)
  {
    if (!vis[i])
    {
      mx_prime_factor[i] = i;
      prime.push_back(i);
    }
    for (int p : prime)
    {
      if (1ll * p * i > n)
        break;
      vis[i * p] = 1;
      mx_prime_factor[i * p] = max(mx_prime_factor[i], p);
      if (i % p == 0)
        break;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++)
    ans += (mx_prime_factor[i] <= B);
  cout << ans;
  return 0;
}