ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2898 - Aizu Competitive Programming Camp 2018 Day 1 C 素数

問題

解法

まずはエラトステネスの篩を適用して範囲内の素数をすべて求めます。
次にpとqのペアですが、素数同士の和が素数になるには、奇数と奇数の素数の和が偶数になる関係上、片方は2で固定されてしまいます。
ということで、片方を2に固定して、もう片方を1からNまで全探索をし、2とqの和が素数であったときに、カウントを2増やします。そして、探索が終わったらそのカウントを出力すれば答えになります。
提出コードはこちらになります。

#include <bits/stdc++.h>
using namespace std;

bool prime[10000005] = {0};

void sprime() {
  int i;
  prime[0] = prime[1] = 1;
  for(i = 2; i < sqrt(10000000); ++i)
    if(!prime[i])
      for(int j = 2; i * j <= 10000000; ++j)
        prime[i * j] = 1;
}

int n;
long long cnt = 0;

int main() {
  int i;
  sprime();
  cin >> n;
  for(i = 2; i <= n; ++i)
    if((!prime[i]) && (!prime[2 + i])) cnt += 2;
  cout << cnt << endl;
  return 0;
}