素数 [Aizu Competitive Programming Camp 2018 Day 1 C]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/C

前提知識

• 素数列挙

考察過程

1. p,q,p+qが全て素数って条件が結構厳しい
2. 2+?に必ずなるな
3. N+2以下の素数を全列挙して、隣り合う素数の差が2であるペアを答えればいい？
4. 双子素数じゃん

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day1/3146212

p,q,p+qが全て素数になるためには、p,qのどちらかが2である必要がある。
2つの隣り合う素数がp, p+2となっているときのみ、p+qがp+2, pがp, qが2となり、条件を満たす。
あとは、N+2以下の素数の列挙だが、エラトステネスの篩を使えばできる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    auto vp = makePrimes(N + 2);
    int ans = 0;
    int n = vp.size();
    rep(i, 0, n - 1) if (vp[i + 1] - vp[i] == 2) ans++;
    cout << ans * 2 << endl;
}