B-smooth 数

题目描述

小杨同学想寻找一种名为 B-smooth 数的正整数。

如果一个正整数的最大质因子不超过 B，则该正整数为 B-smooth 数。小杨同学想知道，对于给定的 n 和 B，有多少个不超过 n 的 B-smooth 数。

输入格式

第一行包含两个正整数 n 和 B，含义如题面所示。

输出格式

输出一个非负整数，表示不超过 n 的 B-smooth 数的数量。

输入输出样例

输入 #1

10 3

输出 #1

7

说明/提示

数据规模与约定

子任务	得分	𝑛≤n≤	𝐵B
1	30	10^3	1≤B≤10^3
2	30	10^6	sqrt(n)​≤B≤10^6
3	40	10^6	1≤B≤10^6

对全部的测试数据，保证 1≤n,B≤10^6。

做法一：线性

#include <iostream>
#include <vector>
using namespace std;vector<int>p;
int n,b;
bool c[1000010],v[1000010];
void init()
{for(int i=2;i<=1000000;i++){if(!c[i]){p.push_back(i);if(i>b)v[i]=true;}for(auto e:p){int t=i*e;if(t>1000000)break;c[t]=true;if(v[i]||v[e])v[t]=true;if(i%e==0)break;}}
}
int main()
{cin>>n>>b;init();int cnt=n;for(int i=1;i<=n;i++)cnt-=v[i];cout<<cnt;return 0;
}

关键词：逆向思维，边筛边算

逆向思维：题目要求的是B-smooth数，我们可以求出非B-smooth数，用n减去这个数量。B-smooth数的定义是最大质因子不超过b，隐含了任何质因子都不超过b，于是非B-smooth数就是有至少一个质因子大于b就够了。

边筛边算：利用筛法特性记录信息。v记录了i是否是非B-smooth数。

---------------------------------------------------------------------------------------------------------------------------------

做法二：埃氏

#include <iostream>
using namespace std;const int m=1000000;
int c[m];
void init()
{for(int i=2;i<=m;i++){if(c[i]==0){c[i]=i;for(int j=2;j<=m;j++){long long t=1ll*i*j;if(t>m)break;c[t]=i;}}}
}
int main()
{init();int n,b;cin>>n>>b;int cnt=0;for(int i=1;i<=n;i++)if(c[i]<=b)cnt++;cout<<cnt;return 0;
}

关键词：夹带私货，适当调整

夹带私货：将原本用于判断i是否是合数，此处我们可以将它改为int类型，用于记录i的最大质因子。这也是由于埃氏筛法的一个性质，每一个数都会被他所有的质因子筛一遍（正版不是这样，后面会说到），所以经过覆盖，c数组中存的数就成了i的最大质因子。

适当调整：正版的埃氏筛不是这样的，第二层循环本应从i开始。虽然这样做效率会高一些，但效率高的原因是每个数只被最小质因子筛了，c数组里存的就成了最小质因子，所以需要省去这个优化才能得出正确结果。

其他：当实在查不出错是重写一遍，要么写着写着发现问题，要么写完就过了……真的！