AtCoder が提供しているABC（AtCoder Beginner Contest）084 D問題をC++で解いてみました。ABC084は、2017年12月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 2017-like Number（Difficulty : 980）
問題の詳細は、リンク先をご覧ください。
素数表を作って、指定された性質の整数を求めます。AtCoder Problems による Difficulty は 980 でした。
解答案
C++ プログラム例（ABC084D）
エラトステネスの篩を用いて、素数表を作ります（4ー31行目）。
その素数表を基に「$N$も $(N+1)/2$ も素数」（2017に似た数）である数の個数の累積和を計算します（44ー52行目）。
区間に含まれる2017に似た数の個数を $O(1)$ の計算量で求めることができます（54ー56行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define N 100000
bool is_prime_table[N + 1];
vector<int> primes;
void generate_primes(int n)
{
is_prime_table[0] = false;
is_prime_table[1] = false;
for (int i = 2; i <= n; ++i) {
is_prime_table[i] = true;
}
for (int i = 2; i * i <= n; ++i) {
if (is_prime_table[i]) {
for (int j = i + i; j <= n; j += i) {
is_prime_table[j] = false;
}
}
}
for (int i = 2; i <= n; ++i) {
if (is_prime_table[i]) {
primes.push_back(i);
}
}
return;
}
int main()
{
int q;
cin >> q;
vector<int> l(q), r(q);
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i];
}
generate_primes(N);
vector<int> sum_like2017(N, 0); /* i番目までの「2017に似た数」の累計和 */
for (int i = 3; i < N; i += 2) {
if (is_prime_table[i] && is_prime_table[(i + 1) / 2]) {
sum_like2017[i] = sum_like2017[i - 2] + 1;
} else {
sum_like2017[i] = sum_like2017[i - 2];
}
sum_like2017[i - 1] = sum_like2017[i - 2];
}
for (int i = 0; i < q; ++i) {
cout << sum_like2017[r[i]] - sum_like2017[l[i] - 1] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
整数について3問続けて解説しました。
- ABC383D問題（解説記事） 素数表を作って、9個約数がある整数を求める。
- ABC052C問題（解説記事） 素因数分解をして、約数の個数を求める。
- ABC084D問題（本日の記事） 素数表を作って、指定された性質の整数を求める。
複数の問題を連続して解説することで、理解を深めることができました。
引き続き ABC の問題を紹介していきます。
