Chương trình đếm số có số ước lẻ trong khoảng cho trước C++

Cho khoảng [a,b]. Đếm số có số lượng ước lẻ. Chỉ các số chính phương mới có số ước lẻ.

Thuật toán

• Cách 1: Duyệt từng số, đếm ước (chậm).
• Cách 2 (tối ưu): Đếm số chính phương trong [a,b] = floor(sqrt(b)) - ceil(sqrt(a)) + 1.

Ví dụ triển khai (C++ - brute force)

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

int OddDivCount(int a, int b) {
    int res = 0;
    for (int i = a; i <= b; ++i) {
        int divCount = 0;
        for (int j = 1; j <= i; ++j)
            if (i % j == 0) ++divCount;
        if (divCount % 2) ++res;
    }
    return res;
}

int main() {
    int a = 1, b = 10;
    cout << OddDivCount(a, b) << endl;
    return 0;
}

Đầu ra

3