問題
ポイント
2以上N以下の整数の素因数の種類を全て求め、最後にK 種類以上の素因数を持つものの個数を
求めます。
方法としては2からNまで全探索していき、素数を見つける度にその素数で割り切れる
N以下の全ての整数の素因数の種類数を+1します。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N, K = map(int, input().split())
# 各数の素因数の種類数を格納
num_prime_factor = [0] * (N+1)
for i in range(2, N+1):
if num_prime_factor[i] != 0: # 0じゃない = 素数じゃないので次のループへ
continue
for j in range(i, N+1, i): # 素数を見つけたらN以下のその素数で割り切れる整数を確認する
num_prime_factor[j] += 1 # 素因数の種類の数を+1する
# K種類以上の素因数を持つものの個数をもとめる
ans = 0
for i in range(len(num_prime_factor)):
if num_prime_factor[i] >= K:
ans += 1
print(ans)
if __name__ == '__main__':
main()
