C++での算術数

算術数は、すべての正の除数の平均が整数である数です。つまり、除数の数が除数の合計を除算できる場合、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 : Calculate the sum of divisors and store into sum variable.
Step 2 : Find the total number of divisors.
Step 3 : Check if the remainder when sum of divisors is divided by the total number of divisors is equal to 0.
Step 4 : If remainder is equal 0. Print YES. Else print 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