Chương trình C++ tìm số có K ước số trong khoảng cho trước

Giới thiệu

Cho ba số nguyên L, R và k. Tìm số lượng số trong khoảng [L, R] có chính xác k ước số (kể cả 1 và chính số đó).

Ví dụ minh họa

Đầu vào

a = 3, b = 10, k = 4

Đầu ra

2

Giải thích

Các số có đúng 4 ước trong khoảng 3-10:
6: ước = 1, 2, 3, 6
8: ước = 1, 2, 4, 8

Phương pháp giải

Duyệt từng số trong khoảng [a, b], đếm ước số của mỗi số. Nếu số ước bằng k thì tăng bộ đếm.

Chương trình minh họa

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

int countDivisors(int n) {
    int divisors = 0;
    for (int i = 1; i <= sqrt(n) + 1; i++) {
        if (n % i == 0) {
            divisors++;
            if (n / i != i)
                divisors++;
        }
    }
    return divisors;
}

int countNumberKDivisors(int a, int b, int k) {
    int numberCount = 0;
    for (int i = a; i <= b; i++) {
        if (countDivisors(i) == k)
            numberCount++;
    }
    return numberCount;
}

int main() {
    int a = 3, b = 10, k = 4;
    cout << "The count of numbers with " << k << " divisors is " << countNumberKDivisors(a, b, k);
    return 0;
}

Đầu ra

The count of numbers with 4 divisors is 2