C++-এ অ্যারিথমেটিক নম্বর

অ্যারিথমেটিক নম্বর হল এমন একটি সংখ্যা যার সব পজিটিভ ডিভাইজার (বিভাজক) গুলোর গড় একটি ইন্টিজার। অর্থাৎ একটি সংখ্যা n-এর জন্য যদি ডিভাইজারদের সংখ্যা ডিভাইজারদের যোগফলকে ভাগ করতে পারে, তবে n হল একটি অ্যারিথমেটিক নম্বর।

উদাহরণ:

Input : n = 6
Output : YES
Explanation :
Divisors are 1, 2, 3, 6
Sum = 1+2+3+6 = 12
Number of divisors = 4
Sum of divisors / number of divisor = 12 / 4 = 3 (ইন্টিজার)

অ্যালগরিদম

Step 1: ডিভাইজারদের যোগফল বের করে sum ভেরিয়েবলে রাখুন।
Step 2: ডিভাইজারদের মোট সংখ্যা বের করুন।
Step 3: চেক করুন ডিভাইজারদের যোগফলকে ডিভাইজারদের সংখ্যা দিয়ে ভাগ করলে ভাগশেষ ০ কিনা।
Step 4: যদি ভাগশেষ ০ হয়, প্রিন্ট YES। অন্যথায় NO।

উদাহরণ কোড

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

void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]) {
    for (int i = 2; i <= n; i++)
        prime[i] = true;
    for (int i = 0; i <= (n * n + 1); i++)
        primesquare[i] = false;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
    int j = 0;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            a[j] = p;
            primesquare[p * p] = true;
            j++;
        }
    }
}

int countDivisors(int n) {
    if (n == 1)
        return 1;
    bool prime[n + 1], primesquare[n * n + 1];
    int a[n];
    SieveOfEratosthenes(n, prime, primesquare, a);
    int ans = 1;
    for (int i = 0;; i++) {
        if (a[i] * a[i] * a[i] > n)
            break;
        int cnt = 1;
        while (n % a[i] == 0) {
            n = n / a[i];
            cnt = cnt + 1;
        }
        ans = ans * cnt;
    }
    if (prime[n])
        ans = ans * 2;
    else if (primesquare[n])
        ans = ans * 3;
    else if (n != 1)
        ans = ans * 4;
    return ans;
}

int sumofFactors(int n) {
    int res = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        int count = 0, curr_sum = 1;
        int curr_term = 1;
        while (n % i == 0) {
            count++;
            n = n / i;
            curr_term *= i;
            curr_sum += curr_term;
        }
        res *= curr_sum;
    }
    if (n >= 2)
        res *= (1 + n);
    return res;
}

আউটপুট

YES