【競プロ】素数と再帰関数

🕒 2019/11/05 🔄 2023/05/01

ここでは、素数の判定に関する処理を、再帰関数を使って書く方法を考えてみます。この処理は、再帰で書く必要は特にありませんが、再帰について学ぶためにあえて再帰を使っています。コードはC++で書いていきます。競プロ記事の一覧はこちら。

📘 目次

素数の判定と再帰関数

2以上の整数 $n$ が与えられたときに、これが素数かどうかを判定する関数を考えてみます。このような処理は、【競プロ】素数と合成数でも行っていますが、ここでは、再帰を使って書くことを考えます。

再帰を使うには、同じ構造でより小さな問題に分解すればいいのでした。今の場合ならどうなるでしょうか。【競プロ】和や階乗と再帰関数などを真似すれば、「 $n$ が素数かどうかを調べるには、 $n-1$ が素数かどうかを調べればいい、、、のか？」などと考えてしまうかもしれません。しかし、これではうまくいきません。 $n$ が素数かどうかと $n-1$ が素数かどうかは、関係がないからです。片方が素数で片方が合成数の時もあるし、両方が合成数の時もあるし、両方が素数の場合もありえます。そのため、今回は、どのように問題を分解すればいいのかを少し考える必要があります。

$n$ が素数であるかどうかは、 $2$ から $n-1$ の中に、約数がないことを調べればいいのでした。つまり、 $2$ でも割り切れず、 $3$ でも割り切れず、…、 $n-1$ でも割り切れない、なら素数だとわかるのでした。この部分であれば再帰で書くことができます。

これを踏まえて、 $n$ が、 $2$ 以上 $k$ 以下のどの整数でも割り切れないことを調べる関数 primeCheck(n, k) を作ってみましょう。問題を次のように分解する、というアイデアです。

　「 $n$ が $2$ でも $3$ でも $4$ でも … $k$ でも割れない」
　＝
　「 $n$ が $k$ で割れない」かつ「 $n$ が $2$ でも $3$ でも $4$ でも … $k-1$ でも割れない」

イコールの前と、イコールの後の後半部分が同じ構造をしています。ここを再帰関数で表現します。

primeCheck(n, k) での処理を考えましょう。n % k の値を調べて、0 だったらその時点で素数でないとわかります。そうでない場合は、さらに primeCheck(n, k - 1) を調べていけばいいですね。

最後に、k == 1 までたどり着けたら、 $2$ 以上 $n-1$ 以下のどの整数でも割り切れなかった、ということなので、素数だとわかります。なので、こうなれば TRUE を返して終了です。

こうすれば、primeCheck(n, k) は、 $n$ が、 $2$ 以上 $k$ 以下のどの整数でも割り切れなければ TRUE、そうでないときは FALSE が返すようになります。primeCheck(n, n - 1) が TRUE なら、n が素数であるということです。

本来なら、素数かどうかを調べるには $n-1$ 以下の整数を調べるべきですが、【競プロ】素数と合成数でみたように、 $\sqrt{n}$ 以下の整数を調べるだけで構いません。つまり、調べ始める値は sqrt(n) でいいです。こうして、次のように書くことができます。

#include <iostream>
#include <cmath>
using namespace std;

bool primeCheck(int n, int k) {
  if (k == 1) return true;
  return (n % k != 0) && primeCheck(n, k - 1);
}

int main() {
  int n; cin >> n;
  if ( primeCheck(n, sqrt(n)) ) cout << "Yes";
  else cout << "No";
  return 0;
}

$2$ 以上の int型の整数を入力すると、素数なら Yes と返ってきて、合成数なら No と返ってきます。

なお、C++では、論理演算子は短絡評価が行われます。つまり、primeCheck の最後にある

  return (n % k != 0) && primeCheck(n, k - 1);

の部分は、左側が FALSE だと右側は評価しません。全体では FALSE となるのが確定するので、それ以上評価しても意味がないからです。このような評価方法を短絡評価と言い、いろんな言語で採用されています。このおかげで、素数じゃないとわかった時点で再帰はストップします。

ここで見た再帰関数は、【競プロ】和や階乗と再帰関数や繰り返し二乗法と再帰関数で見たものとは少し異なっています。それは、数式を使った漸化式で書ける内容ではない、という点です。階乗や繰り返し二乗法では、漸化式で書けるものを再帰関数で表現しましたが、ここで見たように、 TRUE, FALSE を返すだけのような場合でも、再帰関数を使って処理を行えることがあります。

ある値以上の整数のうち最小の素数

先ほどの素数判定の関数を利用して、「ある値以上の整数の中で、最小の素数」を求めるコードをかいてみます。例えば、10 と入力すれば 11 が、20 と入力すれば 23 が返ってくる、というものです。

$2$ 以上の整数 n が入力されたとしましょう。これが素数なら、これを返しておしまいです。もし素数じゃなかったら、この次の数 n + 1 が素数であるかどうかを調べればいいですね。そのため、この処理も再帰関数を使って表すことができます。今までとは異なり、引数をどんどん増やしてて再帰関数を利用するということです。次のようなコードで求めることができます。

#include <iostream>
#include <cmath>
using namespace std;

bool primeCheck(int n, int k) {
  if (k == 1) return true;
  return (n % k != 0) && primeCheck(n, k - 1);
}

int leastPrime(int n) {
  return primeCheck(n, sqrt(n))? n: leastPrime(n + 1);
}

int main() {
  int n; cin >> n;
  cout << leastPrime(n);
  return 0;
}

leastPrime(n) が n 以上の中で最小の素数を返す関数です。この中身は、 n が素数かどうかをチェックして、素数だったら n を、素数でなかったら、その次の値のチェックを行う、つまり、leastPrime(n + 1) を実行するようにしています。

ところで、この処理はいつでも終わるのでしょうか。その答えは、素数の個数について考えるとわかります。

仮に、素数の個数が有限個（例えば $a$ 個）しかないとしましょう。このとき、2以上のどんな整数も、これら $a$ 個の素数のどれかで割り切れるはずです。しかし、 $a$ 個の素数を全部掛け合わせて $1$ を足したものは、 $a$ 個のどの素数でも割り切れません。このことから、有限個ではない、つまり、素数は無限個あることがわかります。

そのため、先ほどの処理は（オーバーフローしない限り）、いつでも n 以上の素数を見つけることができます。