AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の30問目である K Factors（★5）を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【 K Factors（★5）】
入力
N,K 正の整数
考察
今回、制約がN< 10^7です。
そのため、大体O(N)になるようにアルゴリズムを組む必要があります。
計算時間の目安については、こちらの記事がものすごくわかりやすくまとまっているのでご参照ください。
手順
今回で求められることは大きく分けて3つあります。
① 2からNまでの素数を列挙
② 2からNまでにおいて、①で列挙した素数の倍数であるものをカウント
③ ②でカウントした回数がK以上のものを出力
となります。
①の手順
エラトステネスの篩を使用することで、O(Nlog{log(N)})となります。
詳しい解説はこちら
②の手順
素数定理より「Nまでの素数の数は、log(N)/Nに限りなく近似する」となっています。(定理であって定義ではないです)
そのため、2からNまでの素数を約数に持つN以下の数について探索することで手順②の操作を完了できます。
この場合計算量は、
素数の数(log(N)/N)×その素数pがNになるまでに素数pを掛けられた回数log{log(N)}<O(N)
③の手順
最後に2~Nまでの数において、約数に素数をK個以上持つものを出力します
O(N)
典型解法：エラトステネスの篩
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
def list_primes(limit, k=1):# k種類の素因数をもつか返す
have_K_primes = [0]*(limit+1)
is_prime = [True] * (limit + 1)#素数かどうかを判別するリスト
is_prime[0] = False#0は素数じゃないから、False
is_prime[1] = False#1は素数じゃないから、False
#手順1,2
for p in range(0, limit + 1):
if not is_prime[p]: # Falseつまり、素数じゃなければ
continue
# 素数であれば
for i in range(p, limit + 1, p):#その素数の倍数は
is_prime[i] = False#素数ではないので、
have_K_primes[i] += 1#その数は、pという素数を因数に持つ
#手順3
ans = []
for j in range(limit+1):
if have_K_primes[j] >= k:
ans.append(j)
return ans
N,K = MI()
ans = list_primes(N,K)
print(len(ans))まとめ
前の問題【028 – Cluttered Paper（★4）】
次の問題【032 – AtCoder Ekiden（★3）】
コメント