简答题
偏难
#18917
B-smooth数(python) 题面描述 小杨同学想寻找一种名为B-smooth数的正整数。 如果一个正整数的最大质因子不超过B,则该正整数为B-smoot…
B-smooth数(python)
题面描述
小杨同学想寻找一种名为B-smooth数的正整数。
如果一个正整数的最大质因子不超过B,则该正整数为B-smooth数。
小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth数。
输入格式
第一行包含两个正整数n,B,含义如题面所示。
输出格式
输出一个非负整数,表示不超过n的B-smooth数的数量。
样例输入
样例输出
样例解释
在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。
数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n, B = map(int, input().split())
is_prime = [True] * (n + 1)
primes = []
max_prime_factor = [0] * (n + 1)
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
max_prime_factor[i] = i
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
max_prime_factor[i * p] = max(max_prime_factor[i], p)
if i % p == 0:
break
cnt = 0
for i in range(1, n + 1):
if max_prime_factor[i] <= B:
cnt += 1
print(cnt)</pre>
这道题暂未补解析。