Tìm số không phải bình phương thứ N (Non-Square Number) bằng C++

Số không phải bình phương (non-square) là số không thể viết dưới dạng k² với k nguyên. Các số đầu tiên: 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, ...

Ví dụ

Input: 2 Output: 3 (số không bình phương thứ 2 là 3)
Input: 5 Output: 7 (thứ 5 là 7)

Phương pháp

Duyệt số nguyên từ 2 trở đi, kiểm tra xem có phải bình phương hoàn hảo không (bằng cách so sánh i với sqrt(i)²). Đếm các số không phải bình phương cho đến khi đạt N.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int i = 2;
    int cnt = 0;

    while (cnt != n) {
        int a = sqrt(i);
        if (i != a * a)
            cnt++;
        if (cnt != n)
            i++;
    }
    cout << i << "\n";
    return 0;
}

Kết quả

5

(Input 3 → Output 5)

Giải thích

1. Nhập n, khởi tạo i=2 (vì 0,1 là bình phương), cnt=0.
2. Vòng lặp: tính a = sqrt(i). Nếu i != a*a → không phải bình phương → tăng cnt.
3. Nếu chưa đạt n, tăng i và lặp lại.
4. In i khi cnt == n.

Độ phức tạp O(N√N) do hàm sqrt. Có thể tối ưu bằng công thức toán học: số không bình phương thứ N ≈ N + √N.

Kết luận

Bài viết trình bày cách tìm số không bình phương thứ N bằng cách duyệt và kiểm tra. Mã C++ đơn giản, dễ hiểu. Có thể viết bằng Java, Python, C.