Project Euler の問題を解くためにプログラムした関数は、今後も使用できそうです。それらの関数を道具箱として、この記事でまとめておきます。
共通の説明
型は、int にしています。必要に応じて、unsigned int もしくは、unsinged long long int に変更して使います。
引数の確認をさぼっています。不正な入力に対しては正しく動作しません。
素数判定
与えられた自然数が、素数か素数でないかを判定する関数です。
int is_prime(int n)
引数：n 自然数
戻り値：素数なら 1、素数でなければ 0 を返す。
基本版
$\sqrt{n}$ まで調べます。$n$ が大きくなると、$n – 1$ まで調べたり、$n/2$ まで調べる場合と応答時間に大きな差がでます。
int is_prime(int n)
{
int answer = 1;
int i;
if (n == 1) {
answer = 0; /* 1 is not a prime number. */
}
for (i = 2; i * i <= n; ++i) {
if (n % i == 0) {
answer = 0;
break;
}
}
return answer;
}初出は、Project Euler 問題5 です。
素数表版
何回も is_prime を呼び出す場合は、素数表を作っておくと計算量が少なくなる場合があります。エラトステネスの篩を使って素数表を作っておきます。素数を引く上限の値をマクロ定数 N として定義しておきます（1行目）。準備として先に generate_is_prime_table(N); を呼び出しておいてください。is_prime は、マクロ関数として配列の値を返しています（4行目）。
#define N 1000000
unsigned char is_prime_table[N+1];
#define is_prime(n) (is_prime_table[(n)])
void generate_is_prime_table(int n)
{
int i, j;
for (i = 2; i <= n; ++i) {
is_prime_table[i] = 1;
}
for (i = 2; i * i <= n; ++i) {
if (is_prime_table[i] == 1) {
for (j = i + i; j <= n; j += i) {
is_prime_table[j] = 0;
}
}
}
return;
}初出は、Project Euler 問題10 です。
約数の個数を求める
与えられた自然数の約数の個数を返します。
int n_of_divisors(int n)
引数：n 自然数
戻り値：n の約数の個数を返す。
int n_of_divisors(int n)
{
int answer = 0;
int i;
for (i = 1; i * i <= n; ++i) {
if ((n % i) == 0) {
if (i * i != n) {
answer += 2;
} else {
++answer;
}
}
}
return answer;
}初出は、Project Euler 問題12 です。
真の約数の和を求める
与えられた自然数の真の約数（与えられた自然数未満の約数）の和を返します。
int calc_sum_of_divisors(int n)
引数：n 自然数
戻り値：n の真の約数の和を返す。
int calc_sum_of_divisors(int n)
{
int sum;
int i;
sum = 1; /* Add 1 (the first divisor) */
for (i = 2; i * i <= n; ++i) {
if ((n % i) == 0) {
if (i * i != n) {
sum += i;
sum += n / i;
} else {
sum += i;
}
}
}
return sum;
}初出は、Project Euler 問題21 です。
最大公約数を求める
ユークリッドの互除法を使って与えられた自然数 a と b のの最大公約数（GCD: Greatest Common Divisor）を返します。
int gcd(int a, int b)
引数：a, b 自然数
戻り値：a と b の最大公約数を返す。
int gcd(int a, int b)
{
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}初出は、Project Euler 問題5 です。
最後に
ここで紹介した関数は、効率も悪くなく、長く使える道具だと評価しています。このような道具を整備しておくのは、職人が道具を手入れしておく楽しみに通じると考えています。
みなさんも気に入った関数やマクロがあれば、道具箱として整理してはどうでしょうか。
