test/math/Eratosthenes.test.cpp

View this file on GitHub
Last update: 2023-06-18 04:36:16+09:00
Problem: https://yukicoder.me/problems/no/1058

Depends on

Eratosthenes - エラトステネスの篩 (lib/30-math/Eratosthenes.cpp)

Code

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

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#include "../../lib/30-math/Eratosthenes.cpp"

int main() {
    long long N;
    cin >> N;
    auto E = Eratosthenes(200000);
    vector<long long> A;
    for(int i = 100001; i < 100100; ++i) {
        if(E.sieve[i]) A.push_back(i);
    }
    vector<long long> B={1};
    for(auto& e1:A) for(auto& e2:A) B.push_back(e1*e2);
    sort(B.begin(),B.end());
    unique(B.begin(),B.end());
    cout << B[N-1] << endl;
    return 0;
}

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

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#line 1 "lib/30-math/Eratosthenes.cpp"
/*
 * @title Eratosthenes - エラトステネスの篩
 * @docs md/math/Eratosthenes.md
 */
class Eratosthenes {
    unsigned int sz;
public:
    vector<unsigned int> sieve;
    vector<long long> prime;
    Eratosthenes(unsigned int N):sz(N+1),sieve(N+1, 1) {
        sieve[0]=sieve[1]=0;
        for(int i=1; i <= N/i; ++i) if(sieve[i]) for(int j=2*i;j<=N;j+=i) sieve[j]=0;
        for(int i=1; i <= N  ; ++i) if(sieve[i]) prime.push_back(i);
    }
    size_t size() const {
        return sz;
    }
};
#line 8 "test/math/Eratosthenes.test.cpp"

int main() {
    long long N;
    cin >> N;
    auto E = Eratosthenes(200000);
    vector<long long> A;
    for(int i = 100001; i < 100100; ++i) {
        if(E.sieve[i]) A.push_back(i);
    }
    vector<long long> B={1};
    for(auto& e1:A) for(auto& e2:A) B.push_back(e1*e2);
    sort(B.begin(),B.end());
    unique(B.begin(),B.end());
    cout << B[N-1] << endl;
    return 0;
}