จำนวนคณิตศาสตร์ (Arithmetic Number) ใน C++

จำนวนคณิตศาสตร์ (Arithmetic Number) คืออะไร?

จำนวนเต็มบวก n ที่ค่าเฉลี่ยของตัวหารทั้งหมดเป็นจำนวนเต็ม

เงื่อนไข: (ผลรวมตัวหาร) % (จำนวนตัวหาร) == 0

ตัวอย่าง

n = 6

• ตัวหาร: 1, 2, 3, 6
• ผลรวม = 12
• จำนวนตัวหาร = 4
• ค่าเฉลี่ย = 12/4 = 3 (จำนวนเต็ม) → 6 เป็น Arithmetic Number ✓

n = 4

• ตัวหาร: 1, 2, 4
• ผลรวม = 7
• จำนวนตัวหาร = 3
• ค่าเฉลี่ย = 7/3 = 2.33... (ไม่ใช่จำนวนเต็ม) → 4 ไม่ใช่ Arithmetic Number ✗

อัลกอริทึม

1. หาตัวหารทั้งหมดของ n
2. คำนวณผลรวมตัวหาร (σ₁(n))
3. นับจำนวนตัวหาร (σ₀(n))
4. ตรวจสอบ: σ₁(n) % σ₀(n) == 0

ตัวอย่างโค้ด C++ (เวอร์ชันครบถ้วน)

#include <iostream>
#include <cmath>
using namespace std;

// นับจำนวนตัวหาร
int countDivisors(int n) {
    int count = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            count += (i == n / i) ? 1 : 2;
        }
    }
    return count;
}

// หาผลรวมตัวหาร
int sumOfDivisors(int n) {
    int sum = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) sum += n / i;
        }
    }
    return sum;
}

bool isArithmeticNumber(int n) {
    int divCount = countDivisors(n);
    int divSum = sumOfDivisors(n);
    return (divSum % divCount == 0);
}

int main() {
    int n = 46;
    cout << n << " is " << (isArithmeticNumber(n) ? "" : "not ") << "an arithmetic number" << endl;
    
    // แสดง Arithmetic Numbers ตัวแรกๆ
    cout << "\nArithmetic numbers up to 100: ";
    for (int i = 1; i <= 100; i++)
        if (isArithmeticNumber(i)) cout << i << " ";
    return 0;
}

ผลลัพธ์

46 is an arithmetic number

Arithmetic numbers up to 100: 1 3 5 6 7 11 13 14 15 17 19 20 21 22 23 27 29 30 31 33 35 37 38 39 41 42 43 44 45 46 47 49 51 53 54 55 56 57 59 60 61 62 63 65 66 67 68 69 70 71 73 77 78 79 83 85 86 87 89 91 92 93 94 95 97

หมายเหตุประสิทธิภาพ

โค้ดข้างต้นใช้ O(√n) ต่อการตรวจสอบ หากต้องการตรวจสอบหลายจำนวน ให้ใช้ Sieve แบบคำนวณ σ₀ และ σ₁ ล่วงหน้าได้ใน O(n log log n)