Count divisors of array multiplication | Python 3 program to count divisors in array multiplication . ; Create a boolean array " isPrime [ 0 . . n ] " and initialize all entries it as true . A value in isPrime [ i ] will finally be false if i is Not a isPrime , else true . ; If isPrime [ p ] is not changed , then it is a isPrime ; Update all multiples of p ; Print all isPrime numbers ; Returns number of divisors in array multiplication ; Find all prime numbers smaller than the largest element . ; Find counts of occurrences of each prime factor ; Compute count of all divisors using counts prime factors . ; Driver code
from collections import defaultdict NEW_LINE def SieveOfEratosthenes ( largest , prime ) : NEW_LINE INDENT isPrime = [ True ] * ( largest + 1 ) NEW_LINE p = 2 NEW_LINE while p * p <= largest : NEW_LINE INDENT if ( isPrime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , largest + 1 , p ) : NEW_LINE INDENT isPrime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT for p in range ( 2 , largest + 1 ) : NEW_LINE INDENT if ( isPrime [ p ] ) : NEW_LINE INDENT prime . append ( p ) NEW_LINE DEDENT DEDENT DEDENT def countDivisorsMult ( arr , n ) : NEW_LINE INDENT largest = max ( arr ) NEW_LINE prime = [ ] NEW_LINE SieveOfEratosthenes ( largest , prime ) NEW_LINE mp = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( len ( prime ) ) : NEW_LINE INDENT while ( arr [ i ] > 1 and arr [ i ] % prime [ j ] == 0 ) : NEW_LINE INDENT arr [ i ] //= prime [ j ] NEW_LINE mp [ prime [ j ] ] += 1 NEW_LINE DEDENT DEDENT if ( arr [ i ] != 1 ) : NEW_LINE INDENT mp [ arr [ i ] ] += 1 NEW_LINE DEDENT DEDENT res = 1 NEW_LINE for it in mp . values ( ) : NEW_LINE INDENT res *= ( it + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 4 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countDivisorsMult ( arr , n ) ) NEW_LINE DEDENT