Đếm số chính phương và không chính phương trước n trong C++

Cho một số N. Mục tiêu là tìm các cặp thứ tự các số dương sao cho tổng lập phương của chúng bằng N.

Phương pháp đơn giản

Duyệt tất cả số từ 1 đến N và kiểm tra xem nó có phải chính phương không. Nếu floor(sqrt(i)) == ceil(sqrt(i)) thì số đó là chính phương.

Phương pháp hiệu quả

Số chính phương nhỏ hơn N có thể tìm bằng công thức: floor(sqrt(N)).

Hãy hiểu qua các ví dụ.

Đầu vào

N=20

Đầu ra

Số chính phương: 4, Số không chính phương: 16

Giải thích

Các số chính phương: 1, 4, 9, 16. Còn lại đều không chính phương và nhỏ hơn 20.

Đầu vào

N=40

Đầu ra

Số chính phương: 6, Số không chính phương: 34

Giải thích

Các số chính phương: 1, 4, 9, 16, 25, 36. Còn lại đều không chính phương và nhỏ hơn 40.

Phương pháp đơn giản

Phương pháp sử dụng trong chương trình dưới đây

• Nhận số nguyên N.
• Hàm squareNums(int n) nhận n và trả về số lượng số dưới n là chính phương hoặc không chính phương.
• Khởi tạo biến count = 0.
• Duyệt bằng vòng lặp for từ i=1 đến i<=n.
• Nếu floor(sqrt(i)) == ceil(sqrt(i)) thì số đó là chính phương, tăng count.
• Sau tất cả vòng lặp count sẽ chứa tổng số chính phương.
• N - squares sẽ là số không chính phương.

Ví dụ

#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 << "Số chính phương: " << squares;
    cout << endl << "Số không chính phương: " << N - squares;
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số chính phương: 6, Số không chính phương: 34

Phương pháp hiệu quả

Phương pháp sử dụng trong chương trình dưới đây

• Nhận số nguyên N.
• Biến squares = floor(sqrt(N)).
• Biến squares sẽ chứa số lượng chính phương nhỏ hơn N.
• N - squares sẽ là số lượng không chính phương nhỏ hơn N.

Ví dụ

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

int main() {
    int N = 40;
    int squares = floor(sqrt(N));
    cout << endl << "Số chính phương: " << squares;
    cout << endl << "Số không chính phương: " << N - squares;
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số chính phương: 6, Số không chính phương: 34