与えられた数値が互いに素かどうかを判定するC++プログラムの解説

配列 nums に n 個の整数が与えられているとします。ここでの課題は、配列内の数が「ペアワイズ互いに素(pairwise coprime)」「集合的に互いに素(setwise coprime)」「互いに素ではない(not coprime)」のどれに分類されるかを判定することです。

互いに素の定義

• ペアワイズ互いに素: 任意の2つの数 nums[i] と nums[j](i < j)について、gcd(nums[i], nums[j]) = 1 が成り立つとき、配列内の数はペアワイズ互いに素であるといいます。この条件は配列内のすべての数のペアに対して成立しなければなりません。

• 集合的に互いに素: 配列全体の最大公約数が 1、すなわち gcd(nums[0], …, nums[n−1]) = 1 が成り立つとき、これらの数は集合的に互いに素であるといいます。

• 互いに素ではない: 上記のどちらの条件も満たさない場合を指します。

たとえば、入力が n = 4、nums = {7, 11, 13, 17} の場合、出力は「The numbers are pairwise coprime(数はペアワイズ互いに素)」となります。実際、配列内のあらゆる数のペアを調べても gcd は常に 1 になるためです。

アルゴリズムの手順

この問題を解くために、次の手順に従います。

サイズ100の配列 fac を 0 で初期化して定義する。
サイズ100の配列 checkPrime を 0(false)で初期化して定義する。
gcdVal := 0
i := 0 から n 未満の間、i を 1 ずつ増やしながら繰り返す:
    gcdVal := gcd(nums[i], gcdVal)
    fac[nums[i]] := fac[nums[i]] + 1
もし gcdVal が 1 と等しいならば:
    pw := true
    k := 2 から 100 未満の間、k を 1 ずつ増やしながら繰り返す:
        もし checkPrime[k] が真であれば:
            以降をスキップして次の反復へ進む
        c := 0
        j := k から 100 未満の間、j を k ずつ増やしながら繰り返す:
            c := c + fac[j]
            checkPrime[j] := true
        pw := pw AND (c <= 1)
    もし pw が真であれば:
        「The numbers are pairwise coprime」と出力する
    そうでなければ:
        「The numbers are setwise coprime」と出力する
そうでなければ:
    「The numbers are not coprime」と出力する

考え方のポイント

まず配列全体の GCD を累積的に計算します。GCD が 1 でなければ、共通の約数を持つため即座に「not coprime」と判定できます。GCD が 1 の場合は、エラトステネスのふるいに似た手法を使い、各数 k について「k の倍数に該当する要素の出現回数」を数えます。すべての k で出現回数が 1 以下であれば、同じ約数を共有するペアが存在しないことになり、ペアワイズ互いに素であると判断できます。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int nums[]){
   int fac[100] = {0};
   bool checkPrime[100] = {0};
   int gcdVal = 0;
   for(int i = 0; i < n ; i++) {
      gcdVal = __gcd(nums[i], gcdVal);
      ++fac[nums[i]];
   }
   if(gcdVal == 1) {
      bool pw = true;
      for(int k = 2; k < 100; ++k) {
         if(checkPrime[k])
            continue;
         int c = 0;
         for(int j = k; j < 100; j += k) {
            c += fac[j];
            checkPrime[j] = true;
         }
         pw = pw && c <= 1;
      }
      if(pw)
         cout<< "The numbers are pairwise coprime";
      else
         cout<< "The numbers are setwise coprime";
   }
   else
      cout << "The numbers are not coprime";
}
int main() {
   int n = 4, nums[] = {7, 11, 13, 17};
   solve(n, nums);
   return 0;
}

入力

4, {7, 11, 13, 17};

出力

The numbers are pairwise coprime