Số học (Arithmetic Number) trong C++

Số học là số mà trung bình cộng của tất cả ước số dương là số nguyên. Tức là tổng ước số chia hết cho số lượng ước số.

Ví dụ n=6: ước {1,2,3,6}, tổng=12, số lượng=4, 12/4=3 → là số học.

Giải thuật

1. Tính tổng ước số (sum of divisors)
2. Đếm số lượng ước số (count of divisors)
3. Kiểm tra sum % count == 0

Sử dụng sàng Eratosthenes và phân tích thừa số nguyên tố để tính hiệu quả.

Ví dụ minh họa

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

void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]);
int countDivisors(int n);
int sumofFactors(int n);

int main() {
    int n = 46;
    int divCount = countDivisors(n);
    int divSum = sumofFactors(n);
    if (divSum % divCount == 0)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}
// ... (cac ham ho tro Sieve, countDivisors, sumofFactors)

Kết quả

YES