AOJ 1276. Prime Gap

problem

整数$n$に対し$p \le n \le q$な最大/最小の素数$p, q$を考え$q - p$を答えよ。

solution

最初に素数列挙しておいて二分探索。$O(n \log \log n)$。

implementation

#include <algorithm>
#include <cstdio>
#include <vector>
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

vector<bool> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log 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;
    return is_prime;
}
vector<int> list_primes(int n) {
    auto is_prime = sieve_of_eratosthenes(n);
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}

int main() {
    vector<int> primes = list_primes(1299709);
    while (true) {
        int n; scanf("%d", &n);
        if (n == 0) break;
        auto it = whole(lower_bound, primes, n);
        int q = *it;
        int p = *it == n ? *it : *(-- it);
        printf("%d\n", q - p);
    }
    return 0;
}