すべての数値ペアのGCDがKとなるN行の数列を出力する方法

GCD（最大公約数）とは

GCDは「Greatest Common Divisor（最大公約数）」の略で、0以外の2つ以上の整数に共通する約数の中で最も大きいものを指します。

例として、48と180の最大公約数を求めてみましょう。

48 = 2 × 2 × 2 × 2 × 3

180 = 2 × 2 × 3 × 3 × 5

両方の数に共通する素因数は「2 × 2 × 3」であるため、最大公約数は次のように計算できます。

最大公約数 = 2 × 2 × 3 = 12

問題の概要

本記事で扱う問題では、指定された値Kを最大公約数とする要素を含むN行の数列を出力します。各行に含まれるどの2つの数を選んでも、そのGCDが必ずKになるようにするのがポイントです。

入力：N=2 GCD=2
出力：2-4-6-10
14-16-18-22

この出力では、1行目の「2・4・6・10」から任意の2つを選んで組み合わせても（例：2と4、4と10など）、GCDはすべて2になっています。

アルゴリズム

この問題は「6i＋1」「6i＋2」「6i＋3」「6i＋5」という形の数を活用することで解決できます。これらの数は互いに素（GCDが1）の関係にあるため、それぞれにKを掛けることで、任意のペアのGCDが必ずKになります。

START
Step 1 -> 整数n（例：2）とk（例：2）、およびループ変数iをint型として宣言する
Step 2 -> iを0からn未満までループさせる
    Print (k * (6 * i + 1))
    Print (k * (6 * i + 2))
    Print (k * (6 * i + 3))
    Print (k * (6 * i + 5))
    改行（\n）を出力
Step 3 -> ループ終了
STOP

C言語による実装例

#include<stdio.h>
int main() {
    int i,n = 2, k = 2;
    for (i = 0; i < n; i++) {
        printf("%d-",(k * (6 * i + 1)));
        printf("%d-",(k * (6 * i + 2)));
        printf("%d-",(k * (6 * i + 3)));
        printf("%d",(k * (6 * i + 5)));
        printf("\n");
    }
    return 0;
}

このコードでは、行数n＝2、目標のGCDであるk＝2を設定しています。for文のループ内で「6i＋1」「6i＋2」「6i＋3」「6i＋5」にそれぞれkを掛けた値を順番に出力し、1行分の出力が完了するごとに改行しています。

出力結果

上記のプログラムを実行すると、以下の出力が得られます。

2-4-6-10
14-16-18-22

結果を確認すると、1行目の「2・4・6・10」のどの2つの数を選んでも最大公約数は2、2行目の「14・16・18・22」も同様にすべてのペアのGCDが2となっており、条件どおりの動作をしていることがわかります。