範囲 [L, R] 内の互いに素なペアの数え方をわかりやすく解説

この記事では、指定された範囲 [L, R] の中から互いに素な数のペアを数える方法を紹介します。ただし、各数値は最大でも1つのペアにしか使われないものとします。

互いに素な数とは？

ロジックの説明に入る前に、「互いに素な数（コプライム）」という概念を確認しておきましょう。互いに素な数とは、共通の正の約数が 1 だけであるような2つの数の組み合わせのことです。言い換えると、2つの数の最大公約数（GCD）が 1 である関係を指します。

ここでは下限と上限が与えられます。たとえば、下限が 1、上限が 6 の場合、成立するペアは次の3組です。

(1, 2)、(3, 4)、(5, 6)

解法のアプローチ

この問題を解くカギとなるのは、「連続する整数は必ず互いに素である」という性質です。実際、ある整数 n と n + 1 の両方を割り切る数 d が存在すると仮定すると、その差である 1 も d で割り切れることになり、d は 1 以外にあり得ません。したがって、隣り合う整数同士は必ず GCD が 1 になります。

この性質を使うと、答えは非常にシンプルに求められます。範囲内の要素数は (R − L + 1) なので、これを 2 で割った値がペアの個数になります。

• (R − L + 1) が偶数の場合：すべての数がペアを組みます。
• (R − L + 1) が奇数の場合：1つの数が余り、どのペアにも所属しません。

アルゴリズム

countCoPrimePairs(L, R)

Begin
    return (R – L + 1) / 2
End

C++ による実装例

#include <iostream>
using namespace std;
int countCoPrimePairs(int L, int R) {
    return (R - L + 1) / 2;
}
main() {
    int l = 1, r = 6;
    cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r);
}

出力結果

Number of co-prime pairs: 3

このように、連続する整数が常に互いに素になるという数学的な性質を利用すれば、ループや GCD の計算を行うことなく、O(1) の計算量で答えを導き出すことができます。