หาจำนวนตัวหารของทุกจำนวนในช่วง [1, n] ใน C++

ในปัญหานี้ เราได้รับจำนวน N งานของเราคือ การหาจำนวนตัวหารของทุกจำนวนในช่วง [1, n]

ตัวอย่างเพื่อความเข้าใจ

Input : N = 7 
Output : 1 2 2 3 2 4 2

แนวทางแก้ปัญหา

วิธีง่ายคือเริ่มจาก 1 ถึง N สำหรับแต่ละจำนวน ให้นับตัวหารแล้วพิมพ์

ตัวอย่างโค้ด (วิธีที่ 1: นับตัวหารโดยตรง)

#include <iostream>
using namespace std;

int countDivisor(int N) {
    int count = 1;
    for (int i = 2; i <= N; i++) {
        if (N % i == 0)
            count++;
    }
    return count;
}

int main() {
    int N = 8;
    cout << "The number of divisors of all numbers in the range are \t";
    cout << "1 ";
    for (int i = 2; i <= N; i++) {
        cout << countDivisor(i) << " ";
    }
    return 0;
}

ผลลัพธ์

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4

วิธีที่ 2: ใช้การเพิ่มค่าสะสม (Sieve-like Approach) - เร็วกว่า

สร้างอาร์เรย์ขนาด (N+1) เริ่มจาก 1 ถึง N สำหรับแต่ละค่า i ให้เพิ่มค่าในอาร์เรย์สำหรับทุกตัวคูณของ i ที่น้อยกว่าหรือเท่ากับ N

ตัวอย่างโค้ด (วิธีที่ 2)

#include <iostream>
using namespace std;

void countDivisors(int N) {
    int arr[N + 1];
    for (int i = 0; i <= N; i++)
        arr[i] = 1;
    
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j * i <= N; j++)
            arr[i * j]++;
    }
    
    for (int i = 1; i <= N; i++)
        cout << arr[i] << " ";
}

int main() {
    int N = 8;
    cout << "The number of divisors of all numbers in the range are \t";
    countDivisors(N);
    return 0;
}

ผลลัพธ์

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4