test/math/prime_sieve.test.cpp

View this file on GitHub
Last update: 2025-11-15 20:52:05+09:00
Problem: https://yukicoder.me/problems/no/106

Depends on

Required by

test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/106"

#include "../../math/prime_sieve.hpp"
#include "../../template/template.hpp"

int main() {
    int N, K;
    cin >> N >> K;

    PrimeSieve ps(N);

    int ans = 0;
    rep (i, 2, N + 1) {
        auto pf = ps.get_prime_factors(i);

        if (K <= int(pf.size())) {
            ans++;
        }
    }

    cout << ans << LF;

    return 0;
}

#line 1 "test/math/prime_sieve.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/106"

#line 2 "math/prime_sieve.hpp"

#line 2 "template/template.hpp"

/**
 * @author ku_senjan
 * @title 提出用テンプレート
 * @see https://github.com/kogetsu0728/ku-library
 */

#line 2 "template/constant.hpp"

#line 2 "template/include.hpp"

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
#line 2 "template/type_alias.hpp"

#line 4 "template/type_alias.hpp"

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

using ld = long double;

template <class T, bool REVERSE = false>
using heap = priority_queue<T, vector<T>, conditional_t<REVERSE, greater<T>, less<T>>>;
#line 5 "template/constant.hpp"

template <class T>
inline constexpr T INF = numeric_limits<T>::max() / 2;

inline constexpr array<int, 4> DY4 = {0, -1, 0, 1};
inline constexpr array<int, 4> DX4 = {1, 0, -1, 0};
inline constexpr array<int, 8> DY8 = {0, -1, -1, -1, 0, 1, 1, 1};
inline constexpr array<int, 8> DX8 = {1, 1, 0, -1, -1, -1, 0, 1};

inline constexpr char LF = '\n';
#line 2 "template/macro.hpp"

#line 5 "template/macro.hpp"

/**
 * @see https://trap.jp/post/1224/
 */

#ifdef LOCAL
inline constexpr bool IS_LOCAL = true;
#else
inline constexpr bool IS_LOCAL = false;
#endif

#define IF_LOCAL if constexpr (IS_LOCAL)

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define overload4(a, b, c, d, e, ...) e

#define rep1(i, a) for (ll i = 0; (i) < (ll)(a); ++(i))
#define rep2(i, a, b) for (ll i = (ll)(a); (i) < (ll)(b); ++(i))
#define rep3(i, a, b, c) for (ll i = (ll)(a); (i) < (ll)(b); (i) += (ll)(c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(i, a) for (ll i = (ll)(a); (i) >= 0; --(i))
#define rrep2(i, a, b) for (ll i = (ll)(a); (i) >= (ll)(b); --(i))
#define rrep3(i, a, b, c) for (ll i = (ll)(a); (i) >= (ll)(b); (i) -= (ll)(c))
#define rrep(...) overload4(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#line 13 "template/template.hpp"

#line 2 "utility/choose_min_max.hpp"

/**
 * @title Choose Minimum / Maximum
 */

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }

    return false;
}

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}
#line 2 "utility/set_io.hpp"

#line 4 "utility/set_io.hpp"

void set_io(int d = 16) {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(d);

    return;
}
#line 4 "math/prime_sieve.hpp"

/**
 * @brief Prime Sieve (エラトステネスの篩)
 */
class PrimeSieve {
  private:
    vector<int> div, pri;

  public:
    PrimeSieve() : PrimeSieve(0) {}
    PrimeSieve(int _n) : div(_n + 1), pri(0) {
        rep (i, 2, _n + 1) {
            if (div[i] != 0) {
                continue;
            }

            div[i] = i;
            pri.emplace_back(i);

            for (ll j = i * i; j <= ll(_n); j += i) {
                if (div[j] != 0) {
                    continue;
                }

                div[j] = i;
            }
        }
    }

    bool is_prime(const int n) const { return (n < 2) ? false : (div[n] == n); }

    const vector<int>& get_primes() const { return pri; }

    vector<pair<int, int>> get_prime_factors(int n) const {
        vector<pair<int, int>> res;

        while (2 <= n) {
            if (res.empty() || res.back().first != div[n]) {
                res.emplace_back(div[n], 1);
            } else {
                res.back().second++;
            }

            n /= div[n];
        }

        return res;
    }

    vector<int> get_divisors(int n) const {
        vector<int> res;
        res.emplace_back(1);

        auto pf = get_prime_factors(n);

        for (auto [p, q] : pf) {
            int s = res.size();

            rep (i, 0, s) {
                int m = 1;

                rep (j, 0, q) {
                    m *= p;
                    res.emplace_back(res[i] * m);
                }
            }
        }

        sort(all(res));

        return res;
    }
};
#line 5 "test/math/prime_sieve.test.cpp"

int main() {
    int N, K;
    cin >> N >> K;

    PrimeSieve ps(N);

    int ans = 0;
    rep (i, 2, N + 1) {
        auto pf = ps.get_prime_factors(i);

        if (K <= int(pf.size())) {
            ans++;
        }
    }

    cout << ans << LF;

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	input01.txt	AC	72 ms	8 MB
g++	input02.txt	AC	4 ms	4 MB
g++	input03.txt	AC	3 ms	4 MB
g++	input04.txt	AC	3 ms	3 MB
g++	input05.txt	AC	71 ms	8 MB
g++	input06.txt	AC	141 ms	12 MB
g++	input07.txt	AC	141 ms	12 MB
g++	input08.txt	AC	141 ms	12 MB
g++	input09.txt	AC	13 ms	4 MB
g++	input10.txt	AC	13 ms	4 MB
g++	input11.txt	AC	141 ms	12 MB
g++	input12.txt	AC	64 ms	7 MB
g++	input13.txt	AC	134 ms	12 MB
g++	sample01.txt	AC	4 ms	4 MB
g++	sample02.txt	AC	3 ms	4 MB
g++	sample03.txt	AC	3 ms	4 MB