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

ภาพรวมปัญหา

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

ข้อสังเกตสำคัญ

ตัวเลขที่มีจำนวนตัวหารเป็นเลขคี่ ต้องเป็น "จำนวนกำลังสองสมบูรณ์" (Perfect Square) เท่านั้น

เพราะตัวหารมักมาคู่กัน (i และ n/i) ยกเว้นเมื่อ i = √n

ตัวอย่าง

อินพุต

a = 3, b = 10, k = 3

เอาต์พุต

2

คำอธิบาย

4 : ตัวหาร = 1, 2, 4 (3 ตัว)
9 : ตัวหาร = 1, 3, 9 (3 ตัว)

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

ตรวจสอบเฉพาะจำนวนกำลังสองสมบูรณ์ในช่วง [L, R] แล้วนับตัวหาร

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

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

bool isPerfectSquare(int n) {
    int s = sqrt(n);
    return (s * s == n);
}

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 (isPerfectSquare(i))
            if (countDivisors(i) == k)
                numberCount++;
    }
    return numberCount;
}

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

เอาต์พุต

The count of numbers with K odd divisors is 2

สรุป

การกรองเฉพาะ Perfect Square ลดจำนวนการตรวจสอบลงมาก ทำให้เร็วกว่าวิธีตรวจสอบทุกตัว