test/Math/enumerate_primes/yosupo-enumerate_primes.test.cpp

View this file on GitHub
Last update: 2024-09-30 19:12:18+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_primes

Depends on

素数列挙 (Math/enumerate_primes.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes

#include "Math/enumerate_primes.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long N, A, B;
    cin >> N >> A >> B;

    vector<long long> primes = enumerate_primes(N);
    long long piN = primes.size();

    vector<long long> ps;
    for (int i = B; i < piN; i += A)
    {
        ps.push_back(primes[i]);
    }

    long long X = ps.size();

    cout << piN << " " << X << endl;

    for (long long p : ps)
    {
        cout << p << " ";
    }
    cout << endl;

    return 0;
}

#line 1 "test/Math/enumerate_primes/yosupo-enumerate_primes.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_primes

#line 1 "Math/enumerate_primes.hpp"
#include <bits/stdc++.h>
using namespace std;

vector<long long> enumerate_primes(long long n)
{
    assert(0 < n);

    vector<long long> primes;
    vector<bool> isChecked(n + 1, false);
    isChecked[0] = isChecked[1] = true;
    for (long long i = 2; i <= n; i++)
    {
        if (isChecked[i])
        {
            continue;
        }

        primes.push_back(i);
        isChecked[i] = true;

        for (long long j = i * i; j <= n; j += i)
        {
            if (!isChecked[j])
            {
                isChecked[j] = true;
            }
        }
    }

    return primes;
}
#line 5 "test/Math/enumerate_primes/yosupo-enumerate_primes.test.cpp"

using namespace std;

int main()
{
    long long N, A, B;
    cin >> N >> A >> B;

    vector<long long> primes = enumerate_primes(N);
    long long piN = primes.size();

    vector<long long> ps;
    for (int i = B; i < piN; i += A)
    {
        ps.push_back(primes[i]);
    }

    long long X = ps.size();

    cout << piN << " " << X << endl;

    for (long long p : ps)
    {
        cout << p << " ";
    }
    cout << endl;

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	1_00	AC	5 ms	3 MB
g++	2_00	AC	4 ms	3 MB
g++	499477801_00	AC	4218 ms	329 MB
g++	499999993_00	AC	4191 ms	329 MB
g++	example_00	AC	5 ms	3 MB
g++	max_00	AC	4276 ms	329 MB
g++	max_01	AC	4257 ms	329 MB
g++	ten_00	AC	728 ms	83 MB
g++	ten_01	AC	127 ms	24 MB
g++	ten_02	AC	17 ms	5 MB