# 官方题解｜欢乐赛47题解 T6

T6

题意分析

本题是求 $2$ 到 $n$ 中，至少有 $k$ 个质因子的数的个数。可以在埃氏筛法的过程中，不断对每个数求其质因子的个数，最后枚举一下每一个数是否满足有大于等于 $k$ 个质因子即可。

代码

/*
对艾氏筛法的理解
*/
#include <bits/stdc++.h>
using namespace std;
   
const int N = 200010, M = 10000000;
int a[N], n, m, k, cnt, primes[M + 10];
int st[M + 10];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if(!st[i]){
            for(int j = i; j <= n; j += i){
                st[j] ++;
            }
        }
    }
}

int main(){
    int n, k;
    cin >> n >> k;
    get_primes(n);
    for(int i = 1; i <= n; i ++ ){
        if(st[i] >= k){
            cnt ++;
        }
    }
    cout << cnt;
    return 0;
}