C++でN番目の非平方数を求める方法を解説

2、3、5、7、8のように、ある整数の2乗にはならない数(非平方数)は身近にたくさん存在します。しかし非平方数は無限にあるため、そのすべてを把握することはできません。この記事では、非平方数とは何かを丁寧に解説し、C++でN番目の非平方数を求める具体的な方法を紹介します。

N番目の非平方数とは

ある数が別の整数の2乗で表せるとき、その数は完全平方数と呼ばれます。完全平方数の例は以下の通りです。

1 は 1 の2乗
4 は 2 の2乗
9 は 3 の2乗
16 は 4 の2乗
25 は 5 の2乗

一方、どの整数の2乗にもならない数を非平方数と呼びます。最初の15個の非平方数は次のようになります。

2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19

N番目の非平方数の求め方

まず、N番目の非平方数を求める具体例を見てみましょう。

入力 : 2
出力 : 3
説明 : 2番目の非平方数は3です(1番目は2)

入力 : 5
出力 : 7
説明 : 5番目の非平方数は7です(1〜4番目は2、3、5、6)

この例から、N番目の非平方数を求めるには「2から順に整数を調べ、完全平方数であればカウントせずスキップし、非平方数の場合のみカウンタを増やす」というアプローチが有効であることがわかります。

C++でN番目の非平方数を求めるプログラムを作成する

以下に、C++でN番目の非平方数を求めるための完全なサンプルコードを示します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n; // ユーザーから入力を受け取る
    int i = 2; // 0と1は自分自身の2乗なので、2から計算を開始する
    int cnt = 0; // カウンタ変数を宣言
    while(cnt != n){ // カウンタがnと一致したらループを終了する
        int a = sqrt(i);
        if(i != a*a)
            cnt++;
        if(cnt != n)
            i++;
    }
    cout << i << "\n"; // N番目の非平方数を出力する
}

実行結果

5

(入力として3を与えた場合、出力は5になります)

それでは、上記のコードの流れをステップごとに簡単に解説します。

ステップ1 − ユーザーから入力を受け取り、カウンタを0に初期化します。

cin >> n; // ユーザーから入力を受け取る
int i = 2; // 0と1は自分自身の2乗なので、2から計算を開始する
int cnt = 0; // カウンタ変数を宣言

ステップ2 − 非平方数だけをカウントし、完全平方数はスキップします。

while(cnt != n){ // カウンタがnと一致したらループを終了する
    int a = sqrt(i); // sqrt()関数で平方根を求める
    if(i != a*a) // その数が完全平方数かどうかを判定する
        cnt++; // 完全平方数でなければカウンタを増やす
    if(cnt != n)
        i++;
}

ポイントは sqrt(i) の結果を一旦整数 a に代入し、「i == a*a」が成立するかどうかで完全平方数を判定している点です。小数点以下が切り捨てられても元の値と一致すれば、それは完全平方数だと判断できます。

ステップ3 − カウンタがnに達したときのiが答えとなるため、これを出力します。

cout << i << "\n"; // N番目の非平方数を出力する

まとめ

この記事では、非平方数の基本概念と、C++でN番目の非平方数を効率的に求める方法を解説しました。ここで紹介したアルゴリズムの考え方はシンプルなので、Java、Python、Cなど他のプログラミング言語にも容易に応用できます。本記事が皆さんの学習の一助となれば幸いです。