030 - K Factors（★5）
キーワード
解説
素因数列挙の典型問題.
cnt := make([]int, 10000000+1)
for i := 2; i <= n; i++ {
if cnt[i] != 0 {
continue
}
for j := i; j <= n; j += i {
cnt[j]++
}
}各 について, その倍数のcntを ずつ加算していく.
cnt[i] が 0 でないとき, は素数でないことに注意. 逆に,
if cnt[i] != 0 {
continue
}で早期リターンされない は素数.
は の倍数であるため, は を素因数に持つ.
cnt[i]が 以上であるならば, が 種類以上の素因数を持つことがいえる.
例えば, は の倍数列 と の倍数列 の両方に含まれるため, 少なくとも と を素因数に持つことが言える.
提出コード
func main() {
var n, k int
scanIntVariables(&n, &k)
cnt := make([]int, 10000000+1)
for i := 2; i <= n; i++ {
if cnt[i] != 0 {
continue
}
for j := i; j <= n; j += i {
cnt[j]++
}
}
ans := 0
for i := 2; i <= n; i++ {
if cnt[i] >= k {
ans++
}
}
writeLine(ans)
}