Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の1_C問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#1「入門」は、このコースの導入となっています。
問題（1_C: Prime Number）
問題はリンク先をご覧ください。
素数判定について学びます。
素数判定について
この題材は、「C の道具箱ー整数の処理」という記事で紹介していました。
上記の記事は、C言語で記述しました。今回は、関数 is_prime をC++で記述します。$\sqrt{n}$ まで調べています。$n$ が大きくなると、$n-1$ まで調べたり、$n/2$ まで調べる場合と計算量に大きな差がでます。関数は以下となります。
bool is_prime(int n)
{
bool result = true;
if (n == 1) {
result = false; /* 1 is not a prime number. */
}
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
result = false;
break;
}
}
return result;
}C++ プログラム例（ALDS1 1_C）
自然数 n と、n 個の自然数を読み、素数である自然数の数を出力します。上記で紹介した is_prime を順次呼び出して判定しています（30行目）。
以下が、C++プログラムとなります。
#include <iostream>
using namespace std;
bool is_prime(int n)
{
bool result = true;
if (n == 1) {
result = false; /* 1 is not a prime number. */
}
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
result = false;
break;
}
}
return result;
}
int main()
{
int n;
cin >> n;
int result = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (is_prime(x)) {
++result;
}
}
cout << result << endl;
return 0;
}今回の問題は、繰り返し素数判定を行うため、エラトステネスの篩も紹介します。
エラトステネスの篩は、Project Euler 問題10で紹介しています。プログラムはC++に置き換えました。main 関数で素数表を作る generate_is_prime_table を呼び出しています（32行目）。8行目のマクロ関数により、関数 is_prime 版と同じように呼び出せるようにしています（38行目）。エラトステネスの篩は、メモリが必要なことと、素数表を作る時間が必要ですが、素数表ができれば、$O(1)$で素数判定ができます。
#include <iostream>
#include <vector>
using namespace std;
#define N 100000000
vector<bool> is_prime_table(N + 1, false);
#define is_prime(n) (is_prime_table[(n)])
void generate_is_prime_table(int n)
{
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] == true) {
for (int j = i + i; j <= n; j += i) {
is_prime_table[j] = false;
}
}
}
return;
}
int main()
{
int n;
cin >> n;
generate_is_prime_table(N + 1);
int result = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (is_prime(x)) {
++result;
}
}
cout << result << endl;
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
導入の第3段は、素数判定でした。いままでもブログで紹介していた題材でした。自分にとって、頭を整理する良い機会になりました。
引き続き、ALDS1 の問題を紹介していきます。
