Codeforces Round #191 (Div. 2) B. Hungry Sequence

,

B. Hungry Sequence

素数を昇順に$n$個出力すればよい。

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
constexpr int max_prime = 1299709;
using namespace std;
vector<int> eratosthenes_sieve(int N) {
    vector<bool> is_prime(N+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= N; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= N; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= N; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
int main() {
    vector<int> ps = eratosthenes_sieve(max_prime);
    int n; scanf("%d", &n);
    repeat (i,n) {
        if (i) printf(" ");
        printf("%d", ps[i]);
    }
    printf("\n");
    return 0;
}

余談

rubyのprimeを叩いたらTLEした。

#!/usr/bin/env ruby
require 'prime'
n = gets.to_i
puts Prime.take(n).join(' ')