40pts

直接枚举分解质因数

#include<bits/stdc++.h>
using namespace std; 
int main()
{
	int n,b;
	cin>>n>>b;
	int cnt=1;
	for(int i=2;i<=n;i++)
	{
		int t=i;
		int maxv=0;
		for(int j=2;j<=t/j;j++)   //分解质因数 
		{
			while(t%j==0)
			{
				t/=j;
				maxv=max(maxv,j);
			}
		}
		if(t>1) maxv=max(maxv,t);
		if(maxv<=b) //判断是否是B-smooth数 
		{
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

100pts

先筛选所有的质数，然后枚举质数进行分解质因数

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+10;
vector<int> p;
bool st[N];
void get(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!st[i]) p.push_back(i);
		for(int j=0;p[j]<=n/i;j++)
		{
			st[i*p[j]]=1;
			if(i%p[j]==0) break; 
		}
	}
} 
int main()
{
	int n,b;
	cin>>n>>b;
	get(N-1);
	int cnt=1;
	for(int i=2;i<=n;i++)
	{
		int t=i;
		int maxv=0;
		for(int j=0;p[j]<=sqrt(t);j++)   //分解质因数 
		{
			while(t%p[j]==0)
			{
				t/=p[j];
				maxv=max(maxv,p[j]);
			}
		}
		if(t>1) maxv=max(maxv,t);
		if(maxv<=b) //判断是否是B-smooth数 
		{
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

100pts

使用类似倍数法,去枚举所有质数的倍数，然后更新最大的质数

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int maxp[N];
bool st[N];
int main()
{
	int n,b;
	cin>>n>>b;
	for(int i=2;i<=n;i++)
	{
		if(!st[i]) 
		{
			//maxp[i]=i;
			for(int j=i;j<=n;j+=i)
			{
				st[j]=1;
				maxp[j]=max(maxp[j],i);
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		//cout<<i<<" "<<maxp[i]<<endl;
		if(maxp[i]<=b)
		{
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}