C++でNが五角数（ペンタゴナル数）かどうかを判定するプログラム

五角数とは

ある整数 N が与えられたとき、それが五角数（ペンタゴナル数）であるかどうかを判定するのが本記事の目的です。五角数とは、点を並べることで正五角形の形を描くことができる数のことです。これらの数は、五角形を構成する頂点や点として表現できます。

五角数の例としては、次のような数列が挙げられます。

1, 5, 12, 22, 35, 51, 70, 92 …

五角数を判定する公式

ある数が五角数かどうかは、以下の公式を利用して確認できます。

p(n) = (3 × n² − n) / 2

ここで、n は五角形を構成する点の個数を表します。この式から得られる値が順に 1, 5, 12, 22, 35… となり、それぞれが五角数に対応しています。

入力と出力の例

入力： n = 22
出力： 22 は五角数である

入力： n = 23
出力： 23 は五角数ではない

アルゴリズム

開始
ステップ1 → N が五角数かどうかを判定する関数を宣言する
    bool check(int n)
        変数 int i = 1, a を宣言する
        do
            a = (3 * i * i - i) / 2 を代入する
            i += 1 とする
        while (a < n);
        return (a == n);
ステップ2 → main() 内で
    int n = 22 を宣言する
    if (check(n)) の場合
        「五角数である」と出力する
    終了
    else の場合
        「五角数ではない」と出力する
    終了
停止

C++での実装例

#include <iostream>
using namespace std;
// N が五角数かどうかを判定する関数
bool check(int n){
    int i = 1, a;
    do{
        a = (3*i*i - i)/2;
        i += 1;
    }
    while (a < n);
    return (a == n);
}
int main(){
    int n = 22;
    if (check(n))
        cout << n << " is pentagonal " << endl;
    else
        cout << n << " is not pentagonal" << endl;
    return 0;
}

実行結果

22 is pentagonal

プログラムの仕組み

このプログラムでは、check 関数内で i を 1 から順に増やしながら、公式 p(i) = (3i² − i) / 2 によって五角数を生成していきます。生成された値 a が入力値 n 以上になった時点でループを終了し、a が n と一致していれば n は五角数であると判断できます。

例えば n = 22 の場合、i = 4 のとき a = (3×16 − 4) / 2 = 22 となるため、「22 は五角数である」という結果が出力されます。一方、n = 23 の場合はどの i に対しても a が 23 にならないため、五角数ではないと判定されます。

この手法の計算量は O(√n) 程度であり、五角数はおおよそ n の平方根に比例して増加するため、大きな数に対しても効率的に判定できるのが特徴です。