Querying maximum number of divisors that a number in a given range has | Python 3 implementation of the above idea to process queries of finding a number with maximum divisors . ; Finds smallest prime factor of allnumbers in range [ 1 , maxn ) and stores them in smallest_prime [ ] , smallest_prime [ i ] should contain the smallest prime that divides i ; Initialize the smallest_prime factors of all to infinity ; to be built like eratosthenes sieve ; prime number will have its smallest_prime equal to itself ; if ' i ' is the first prime number reaching 'j ; number of divisors of n = ( p1 ^ k1 ) * ( p2 ^ k2 ) . . . ( pn ^ kn ) are equal to ( k1 + 1 ) * ( k2 + 1 ) . . . ( kn + 1 ) . This functionfinds the number of divisors of all numbersin range [ 1 , maxn ) and stores it in divisors [ ] divisors [ i ] stores the number of divisors i has ; we can obtain the prime factorization of the number n n = ( p1 ^ k1 ) * ( p2 ^ k2 ) . . . ( pn ^ kn ) using the smallest_prime [ ] array , we keep dividing n by its smallest_prime until it becomes 1 , whilst we check if we have need to set k zero ; use p ^ k , initialize k to 0 ; builds segment tree for divisors [ ] array ; leaf node ; build left and right subtree ; combine the information from left and right subtree at current node ; returns the maximum number of divisors in [ l , r ] ; If current node 's range is disjoint  with query range ; If the current node stores information for the range that is completely inside the query range ; Returns maximum number of divisors from left or right subtree ; Driver code ; First find smallest prime divisors for all the numbers ; Then build the divisors [ ] array to store the number of divisors ; Build segment tree for the divisors [ ] array
maxn = 1000005 NEW_LINE INF = 99999999 NEW_LINE smallest_prime = [ 0 ] * maxn NEW_LINE divisors = [ 0 ] * maxn NEW_LINE segmentTree = [ 0 ] * ( 4 * maxn ) NEW_LINE def findSmallestPrimeFactors ( ) : NEW_LINE INDENT for i in range ( maxn ) : NEW_LINE INDENT smallest_prime [ i ] = INF NEW_LINE DEDENT for i in range ( 2 , maxn ) : NEW_LINE INDENT if ( smallest_prime [ i ] == INF ) : NEW_LINE INDENT smallest_prime [ i ] = i NEW_LINE for j in range ( i * i , maxn , i ) : NEW_LINE DEDENT DEDENT DEDENT ' NEW_LINE INDENT if ( smallest_prime [ j ] > i ) : NEW_LINE INDENT smallest_prime [ j ] = i NEW_LINE DEDENT DEDENT def buildDivisorsArray ( ) : NEW_LINE INDENT for i in range ( 1 , maxn ) : NEW_LINE INDENT divisors [ i ] = 1 NEW_LINE n = i NEW_LINE p = smallest_prime [ i ] NEW_LINE k = 0 NEW_LINE while ( n > 1 ) : NEW_LINE INDENT n = n // p NEW_LINE k += 1 NEW_LINE if ( smallest_prime [ n ] != p ) : NEW_LINE INDENT divisors [ i ] = divisors [ i ] * ( k + 1 ) NEW_LINE k = 0 NEW_LINE DEDENT p = smallest_prime [ n ] NEW_LINE DEDENT DEDENT DEDENT def buildSegtmentTree ( node , a , b ) : NEW_LINE INDENT if ( a == b ) : NEW_LINE INDENT segmentTree [ node ] = divisors [ a ] NEW_LINE return NEW_LINE DEDENT buildSegtmentTree ( 2 * node , a , ( a + b ) // 2 ) NEW_LINE buildSegtmentTree ( 2 * node + 1 , ( ( a + b ) // 2 ) + 1 , b ) NEW_LINE segmentTree [ node ] = max ( segmentTree [ 2 * node ] , segmentTree [ 2 * node + 1 ] ) NEW_LINE DEDENT def query ( node , a , b , l , r ) : NEW_LINE INDENT if ( l > b or a > r ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( a >= l and b <= r ) : NEW_LINE INDENT return segmentTree [ node ] NEW_LINE DEDENT return max ( query ( 2 * node , a , ( a + b ) // 2 , l , r ) , query ( 2 * node + 1 , ( ( a + b ) // 2 ) + 1 , b , l , r ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT findSmallestPrimeFactors ( ) NEW_LINE buildDivisorsArray ( ) NEW_LINE buildSegtmentTree ( 1 , 1 , maxn - 1 ) NEW_LINE print ( " Maximum ▁ divisors ▁ that ▁ a ▁ number ▁ has ▁ " , " ▁ in ▁ [ 1 , ▁ 100 ] ▁ are ▁ " , query ( 1 , 1 , maxn - 1 , 1 , 100 ) ) NEW_LINE print ( " Maximum ▁ divisors ▁ that ▁ a ▁ number ▁ has " , " ▁ in ▁ [ 10 , ▁ 48 ] ▁ are ▁ " , query ( 1 , 1 , maxn - 1 , 10 , 48 ) ) NEW_LINE print ( " Maximum ▁ divisors ▁ that ▁ a ▁ number ▁ has " , " ▁ in ▁ [ 1 , ▁ 10 ] ▁ are ▁ " , query ( 1 , 1 , maxn - 1 , 1 , 10 ) ) NEW_LINE DEDENT