Arithmetic Number | Python3 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. ; for storing primes upto n ; 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 ; 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 ; 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 . ; Driver code
import math NEW_LINE def SieveOfEratosthenes ( n , prime , primesquare , a ) : NEW_LINE INDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT prime [ i ] = True ; NEW_LINE DEDENT for i in range ( ( n * n + 1 ) + 1 ) : NEW_LINE INDENT primesquare [ i ] = False ; NEW_LINE DEDENT prime [ 1 ] = False ; NEW_LINE p = 2 ; NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False ; NEW_LINE DEDENT DEDENT p += 1 ; NEW_LINE DEDENT j = 0 ; NEW_LINE for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT a [ j ] = p ; NEW_LINE primesquare [ p * p ] = True ; NEW_LINE j += 1 ; NEW_LINE DEDENT DEDENT DEDENT def countDivisors ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT prime = [ False ] * ( n + 2 ) ; NEW_LINE primesquare = [ False ] * ( n * n + 3 ) ; NEW_LINE a = [ 0 ] * n ; NEW_LINE SieveOfEratosthenes ( n , prime , primesquare , a ) ; NEW_LINE ans = 1 ; NEW_LINE for i in range ( 0 , True ) : NEW_LINE INDENT if ( a [ i ] * a [ i ] * a [ i ] > n ) : NEW_LINE INDENT break ; NEW_LINE DEDENT cnt = 1 ; NEW_LINE while ( n % a [ i ] == 0 ) : NEW_LINE INDENT n //= a [ i ] ; NEW_LINE cnt = cnt + 1 ; NEW_LINE DEDENT ans = ans * cnt ; NEW_LINE DEDENT if ( prime [ n ] ) : NEW_LINE INDENT ans = ans * 2 ; NEW_LINE DEDENT elif ( primesquare [ n ] ) : NEW_LINE INDENT ans = ans * 3 ; NEW_LINE DEDENT elif ( n != 1 ) : NEW_LINE INDENT ans = ans * 4 ; NEW_LINE DEDENT DEDENT def sumofFactors ( n ) : NEW_LINE INDENT res = 1 ; NEW_LINE for i in range ( 2 , int ( math . sqrt ( n ) ) + 1 ) : NEW_LINE INDENT count = 0 ; NEW_LINE curr_sum = 1 ; NEW_LINE curr_term = 1 ; NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT count += 1 ; NEW_LINE n //= i ; NEW_LINE curr_term *= i ; NEW_LINE curr_sum += curr_term ; NEW_LINE DEDENT res *= curr_sum ; NEW_LINE DEDENT if ( n >= 2 ) : NEW_LINE INDENT res *= ( 1 + n ) ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT def checkArithmetic ( n ) : NEW_LINE INDENT count = countDivisors ( n ) ; NEW_LINE sum = sumofFactors ( n ) ; NEW_LINE return ( sum % count == 0 ) ; NEW_LINE DEDENT n = 6 ; NEW_LINE if ( checkArithmetic ( n ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) ; NEW_LINE DEDENT