Minimise N such that sum of count of all factors upto N is greater than or equal to X | Python3 program for the above approach ; Array to store smallest prime factors of each no . ; Function to calculate smallest prime factor of N . ; Marking spf [ j ] if it is not previously marked ; Array to store the count of factor for N ; Prefix array which contains the count of factors from 1 to N ; Function to count total factors from 1 to N ; Store total factors of i ; Stores total factors from 1 to i ; Function to search lowest X such that the given condition is satisfied ; Find mid ; Search in the right half ; Search in the left half ; Return the position after Binary Search ; Function to find the required sum ; Precompute smallest prime factor of each value ; Calculate count of total factors from 1 to N ; Binary search to find minimum N ; Driver code ; Given Sum ; Function Call
MAX = 1000050 NEW_LINE spf = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE def calculate_SPF ( ) : NEW_LINE INDENT for i in range ( MAX + 1 ) : NEW_LINE INDENT spf [ i ] = i ; NEW_LINE DEDENT for i in range ( 4 , MAX + 1 , 2 ) : NEW_LINE INDENT spf [ i ] = 2 ; NEW_LINE DEDENT i = 3 NEW_LINE while ( i * i <= MAX ) : NEW_LINE INDENT if ( spf [ i ] == i ) NEW_LINE INDENT j = i * i NEW_LINE while ( j <= MAX ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i ; NEW_LINE DEDENT j += i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT tfactor = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE pre = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE def CountTotalfactors ( ) : NEW_LINE INDENT tfactor [ 1 ] = pre [ 1 ] = 1 ; NEW_LINE for i in range ( 2 , MAX + 1 ) : NEW_LINE INDENT mspf = spf [ i ] ; NEW_LINE prim = mspf ; NEW_LINE temp = i ; NEW_LINE cnt = 0 ; NEW_LINE while ( temp % mspf == 0 ) : NEW_LINE INDENT temp //= mspf ; NEW_LINE cnt += 1 ; NEW_LINE prim = prim * mspf ; NEW_LINE DEDENT tfactor [ i ] = ( cnt + 1 ) * NEW_LINE INDENT tfactor [ temp ] ; NEW_LINE DEDENT pre [ i ] = pre [ i - 1 ] + NEW_LINE INDENT tfactor [ i ] ; NEW_LINE DEDENT DEDENT DEDENT def BinarySearch ( X ) : NEW_LINE INDENT start = 1 ; NEW_LINE end = MAX - 1 ; NEW_LINE while ( start < end ) : NEW_LINE INDENT mid = ( start + end ) // 2 ; NEW_LINE if ( pre [ mid ] == X ) : NEW_LINE INDENT return mid ; NEW_LINE DEDENT elif ( pre [ mid ] < X ) : NEW_LINE INDENT start = mid + 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT end = mid ; NEW_LINE DEDENT DEDENT return start ; NEW_LINE DEDENT def findSumOfCount ( X ) : NEW_LINE INDENT calculate_SPF ( ) ; NEW_LINE CountTotalfactors ( ) ; NEW_LINE print ( BinarySearch ( X ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT X = 10 ; NEW_LINE findSumOfCount ( X ) ; NEW_LINE DEDENT