Kiểm tra số chính phương (Perfect Square)

Giới thiệu

Một số được gọi là số chính phương nếu căn bậc hai của số đó là số nguyên. Nói cách khác, khi căn bậc hai là số nguyên, thì số đó gọi là số chính phương.

Ta có thể kiểm tra số chính phương bằng cách tìm căn bậc hai của số đó và đối chiếu với i liên tục để tìm căn chính xác. Khi căn bậc hai vượt quá giá trị, đó không phải số chính phương.

Nhưng ở đây để giảm công sức, ta không kiểm tra căn bậc hai liên tục. Vì ta biết căn bậc hai của số chính phương là số nguyên, ta có thể tăng căn bậc hai lên một đơn vị và kiểm tra sự khớp của số chính phương.

Đầu vào và Đầu ra

Đầu vào: Số cần kiểm tra: 1032
Đầu ra: 1032 không phải là số chính phương.

Thuật toán

isPerfectSquare(num)
Đầu vào: Số cần kiểm tra.
Đầu ra: True nếu số là chính phương, và in ra căn bậc hai.

Begin
    if num < 0, then
        exit
    sqRoot := 1
    sq := sqRoot^2
    while sq <= num, do
        if sq = num, then
            return sqRoot
        sqRoot := sqRoot + 1
        sq := sqRoot^2
    done
    otherwise return error
End

Ví dụ (C++)

#include <iostream>
using namespace std;

int isPerfectSquare(int num) {
    if(num < 0)
        return -1;  // số âm không phải hạng mục vuông hợp lệ
    int sqRoot = 1, sq;
    while((sq = (sqRoot*sqRoot)) <= num) {
        // khi bình phương căn bậc hai chưa vượt quá số
        if(sq == num)
            return sqRoot;
        sqRoot++;  // vì căn bậc hai của số chính phương luôn là số nguyên
    }
    return -1;
}

int main() {
    int num, res;
    cout << "Enter a number to check whether it is perfect square or not: ";
    cin >> num;
    if((res = isPerfectSquare(num)) != -1)
        cout << num << " is a perfect square number, square root: " << res;
    else
        cout << num << " is not a perfect square number.";
}

Kết quả

Enter a number to check whether it is perfect square or not: 1032
1032 is not a perfect square number.