平方数の判定をするアルゴリズム
Nが自然数の2乗で表現できるとき、平方数と言います。
- 平方数の例
- 4 (= 2×2)
- 9 (= 3×3)
- 16 (= 4×4)
- 25 (= 5×5)
アルゴリズム
以下の方法以外にも色々な求め方があるかと思いますが、代表的な求め方をまとめました。以下の他にも、「二分探索で \(k^2 \leq N\) となる最大の \(k\) を探索する方法」などが考えられると思います。
全探索でのアルゴリズム：
- \(\sqrt{N}\) 以下の自然数 \(k\) に対して以下を確かめる
- \(k^2 = N\) となる \(k\) が存在すれば N は平方数
※ 平方数なら、\(k^2 = N\) となる \(\sqrt{N}\) 以下の自然数 \(k\) が必ず存在するので、それを探索します。
約数の個数を利用したアルゴリズム：
- Nの約数の個数を求める
- 約数の個数が奇数なら平方数、偶数なら平方数ではない。
※ 約数の個数の求め方については、こちらを参照してください。
※ 奇数か偶数かの判定は、2 で割り切れるかどうかを確認すればよいです。
※ 平方数の約数の個数は必ず奇数になります。以下は平方数 36 の約数を並べた時の図です。
平方根を利用したアルゴリズム：
- N の平方根 r を計算する
- r を「切り捨て or 切り上げ or 四捨五入」した数を2乗する。これがNに一致すれば平方数、一致しなければ平方数ではない。
※ 平方数なら r は必ず整数なので「切り捨て or 切り上げ or 四捨五入」のどれを行っても r が変化しません。平方数でなければ r が小数から整数になるので必ず変化してしまいます。
※ 例えば、36 の平方根は 6 で、これは「切り捨て or 切り上げ or 四捨五入」のどれを行っても 6 のままです。2乗すると 36 に一致します。
計算量
全探索でのアルゴリズム
- \(O(\sqrt{N})\)
全ての \(\sqrt{N}\) 以下の自然数 \(k\) を確かめることになるので、全体としては \(O(\sqrt{N})\) になります。
約数の個数を利用したアルゴリズム
- 前処理なしのアルゴリズム
- 前処理：なし
- クエリ：\(O(\sqrt{N})\)
- 前処理ありのアルゴリズム
- 前処理：\(O(N \log \log N)\)
- クエリ：\(O(\log N)\)
約数の個数をどのように求めるかで計算量が変わってきます。（詳細：Nの約数の個数を求めるアルゴリズム）
奇数か偶数かの判定は \(O(1)\) でできるので、全体には影響しません。
平方根を利用したアルゴリズム
一般的には約数の個数を利用したアルゴリズムよりも高速です。
計算量は平方根をどれだけの速度で計算できるかによって変化します。コンピュータによって違うこともありますし、プログラミング言語でサポートされている sqrt() 関数の速度にも依ります。
自分で二分法などのアルゴリズムを使って平方根を求めることも可能です（どれくらいの誤差を許すかで計算時間も変化します）。
C++ での実装例
約数の個数を利用したアルゴリズム
約数の個数を求めるために、素因数分解を利用しています。前処理はしていません。
#include <bits/stdc++.h>
using namespace std;
// 素因数分解
template <typename T>
map<T, T> prime_factor(T n) {
map<T, T> ret;
for (T i = 2; i * i <= n; i++) {
T tmp = 0;
while (n % i == 0) {
tmp++;
n /= i;
}
ret[i] = tmp;
}
if (n != 1) ret[n] = 1;
return ret;
}
// 約数の個数を求める
template <typename T>
T divisor_num(T N) {
map<T, T> pf = prime_factor(N);
T ret = 1;
for (auto p : pf) {
ret *= (p.second + 1);
}
return ret;
}
// 平方数かどうかの判定
bool is_squere(long long N) {
return divisor_num(N) % 2 == 1;
}
long long N;
int main() {
cin >> N;
if (is_squere(N)) {
cout << "square" << endl;
} else {
cout << "not square" << endl;
}
return 0;
}
平方根を利用したアルゴリズム
整数で計算するか、浮動小数点で計算するか注意する必要があります。
平方根を計算する時は浮動小数点で計算する必要がありますが、切り捨て・切り上げ・四捨五入などを行ったら整数型にして計算するのが良いでしょう。
#include <bits/stdc++.h>
using namespace std;
// 平方数かどうかの判定
bool is_squere(long long N) {
long long r = (long long)floor(sqrt((long double)N)); // 切り捨てした平方根
return (r * r) == N;
}
long long N;
int main() {
cin >> N;
if (is_squere(N)) {
cout << "square" << endl;
} else {
cout << "not square" << endl;
}
return 0;
}