หาจำนวนที่มีตัวหาร K ตัวในช่วงที่กำหนดด้วย C++

ภาพรวมปัญหา

ได้รับค่า L, R, และ k ต้องหาจำนวนของตัวเลขในช่วง [L, R] ที่มีตัวหารทั้งหมด k ตัว (นับ 1 และตัวมันเองด้วย)

ตัวอย่าง

อินพุต

a = 3, b = 10, k = 4

เอาต์พุต

2

คำอธิบาย

ตัวเลขที่มีตัวหาร 4 ตัวในช่วง 3-10:
6 : ตัวหาร = 1, 2, 3, 6
8 : ตัวหาร = 1, 2, 4, 8

วิธีแก้ปัญหา

นับตัวหารของแต่ละตัวเลขในช่วง [L, R] โดยวนจาก 1 ถึง √n

โค้ดตัวอย่าง

#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;
}

เอาต์พุต

The count of numbers with 4 divisors is 2

สรุป

อัลกอริทึมนับตัวหารโดยวนจนถึง √n ให้ Complexity ประมาณ O((R-L+1) × √R)