Arithmetic Number | CPP program to check if a number is Arithmetic number or not ; Sieve Of Eratosthenes ; 1 is not a prime number ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Storing primes in an array ; Update value in primesquare [ p * p ] , if p is prime . ; Function to count divisors ; If number is 1 , then it will have only 1 as a factor . So , total factors will be 1. ; Calling SieveOfEratosthenes to store prime factors of n and to store square of prime factors of n ; ans will contain total number of distinct divisors ; Loop for counting factors of n ; a [ i ] is not less than cube root n ; Calculating power of a [ i ] in n . cnt is power of prime a [ i ] in n . ; if a [ i ] is a factor of n ; cnt = cnt + 1 ; incrementing power ; Calculating number of divisors If n = a ^ p * b ^ q then total divisors of n are ( p + 1 ) * ( q + 1 ) ; First case ; Second case ; Third casse ; return ans ; Total divisors ; Returns sum of all factors of n . ; Traversing through all prime factors . ; This condition is to handle the case when n is a prime number greater than 2. ; Check if number is Arithmetic Number or not . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ] ; 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 ] ; } ans = ans * cnt ; } if ( prime [ n ] ) ans = ans * 2 ; else if ( primesquare [ n ] ) ans = ans * 3 ; else if ( n != 1 ) ans = ans * 4 ; } 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 ; } bool checkArithmetic ( int n ) { int count = countDivisors ( n ) ; int sum = sumofFactors ( n ) ; return ( sum % count == 0 ) ; } int main ( ) { int n = 6 ; ( checkArithmetic ( n ) ) ? ( cout << " Yes " ) : ( cout << " No " ) ; return 0 ; }