【C++】N以下の平方数と非平方数の個数を求める方法

整数 N が与えられたとき、1 から N の範囲に含まれる平方数（完全平方数）と非平方数の個数をそれぞれ求めるのが本記事の目的です。

素朴なアプローチ（Naive Approach）

1 から N までのすべての数を順番に走査し、各数が完全平方数かどうかを判定します。判定には次の条件を使用します。

floor(sqrt(i)) == ceil(sqrt(i))

この等式が成立する場合、その数は完全平方数であると判断できます。

効率的なアプローチ（Efficient Approach）

N 以下の完全平方数は、次の式ひとつで求められます。

floor(sqrt(N))

この値がそのまま平方数の個数となり、N − 平方数の個数が非平方数の個数になります。

実行例

入力

N = 20

出力

平方数の個数: 4
非平方数の個数: 16

解説

20 以下の平方数は 1, 4, 9, 16 の 4 つです。残りの 16 個はすべて非平方数です。

入力

N = 40

出力

平方数の個数: 6
非平方数の個数: 34

解説

40 以下の平方数は 1, 4, 9, 16, 25, 36 の 6 つです。残りの 34 個はすべて非平方数です。

素朴なアプローチの実装

プログラムの流れ

• 整数 N を受け取ります。

• 関数 squareNums(int n) は、n 以下の数のうち完全平方数の個数を返します。

• カウント用の変数 count を 0 で初期化します。

• for ループで i = 1 から i <= n まで走査します。

• floor(sqrt(i)) == ceil(sqrt(i)) が成立すれば i は完全平方数なので、count をインクリメントします。

• ループ終了後、count には完全平方数の総数が格納されています。

• N − count が非平方数の個数となります。

サンプルコード

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int squareNums(int n){
    int count = 0;
    for (int i = 1; i <= n; i++){
        if(floor(sqrt(i))==ceil(sqrt(i)))
            { count++; }
    }
    return count;
}
int main(){
    int N = 40;
    int squares=squareNums(N);
    cout <<endl<<"平方数の個数: "<<squares;
    cout <<endl<<"非平方数の個数: "<<N-squares;
    return 0;
}

出力

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

平方数の個数: 6
非平方数の個数: 34

効率的なアプローチの実装

プログラムの流れ

• 整数 N を受け取ります。

• squares = floor(sqrt(N)) を計算します。

• 変数 squares には N 以下の完全平方数の個数が入ります。

• N − squares が非平方数の個数となります。

この方法ではループ処理が不要のため、計算量は O(1)。N が非常に大きい場合でも高速に答えを求められる点が大きなメリットです。

サンプルコード

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int N = 40;
    int squares=floor(sqrt(N));
    cout <<endl<<"平方数の個数: "<<squares;
    cout <<endl<<"非平方数の個数: "<<N-squares;
    return 0;
}

出力

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

平方数の個数: 6
非平方数の個数: 34