C++で数がプロス数（Proth数）かどうかを判定するプログラム

ある正の整数「n」が与えられたとき、その数がプロス数（Proth数）であるかどうかを判定し、結果を出力するのが本記事のテーマです。

プロス数とは？

プロス数とは、次の形で表される数のことです。

N = k × 2ⁿ + 1

ここで、n は正の整数、k は奇数の正の整数です。

最初のいくつかのプロス数は以下の通りです。

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97.......

入力

number: 17

出力

its a proth number（プロス数です）

入力

number: 18

出力

its not a proth number（プロス数ではありません）

プログラムのアプローチ

• 判定したい数を入力として受け取る

• プロス数の定義式に基づき、その数がプロス数かどうかを判定する

• 条件が成立すれば「プロス数である」と出力する

• 条件が成立しなければ「プロス数ではない」と出力する

アルゴリズム

ステップ1→ 2のべき乗かどうかを判定する関数を宣言する
    bool isPower(int num)
       return (num && !(num & (num - 1)))
ステップ2→ 数がプロス数かどうかを判定する関数を宣言する
    bool isProth(int num)
       int k = 1 を宣言
       While (k < (num / k))
          IF (num % k == 0)
             IF (isPower(num / k))
                return true
             End
          End
          k = k + 2 を設定
       End
       return false
ステップ3→ main() 内での処理
    int num = 17 を宣言
    IF (isProth(num - 1))
       "its a proth number" を出力
    Else
       "its not a proth number" を出力
終了

コード例

#include <bits/stdc++.h>
using namespace std;
// 2のべき乗かどうかを判定する関数
bool isPower(int num){
    return (num && !(num & (num - 1)));
}
// 数がプロス数かどうかを判定する関数
bool isProth(int num){
    int k = 1;
    while (k < (num / k)){
        if (num % k == 0){
            if (isPower(num / k))
                return true;
        }
        k = k + 2;
    }
    return false;
}
int main(){
    int num = 17;
    if (isProth(num - 1))
        cout << "its a proth number";
    else
        cout << "its not a proth number";
    return 0;
}

コードのポイント

isPower() 関数では、ビット演算を利用して 2 のべき乗を効率的に判定しています。「num と num − 1 の論理積（AND）が 0 になるなら、num は 2 のべき乗である」という性質を使った定番テクニックです。

また、main() 内で isProth(num - 1) を呼び出しているのは、「num がプロス数である ⟺ num − 1 が k × 2ⁿ の形に分解できる」という性質を利用するためです。num − 1 を奇数 k と 2 のべき乗の積に分解できれば、num はプロス数だと判定できます。

出力

上記のコードを実行すると、次の出力が得られます。

its a proth number

これは、17 がプロス数（17 = 1 × 2⁴ + 1）であることを示しています。