Minimise N such that sum of count of all factors upto N is greater than or equal to X | Java 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
import java . util . * ; class GFG { static final int MAX = 1000050 ; static int [ ] spf = new int [ MAX + 1 ] ; static void calculate_SPF ( ) { for ( int i = 0 ; i <= MAX ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i <= MAX ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i <= MAX ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j <= MAX ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } static int [ ] tfactor = new int [ MAX + 1 ] ; static int [ ] pre = new int [ MAX + 1 ] ; static void CountTotalfactors ( ) { tfactor [ 1 ] = pre [ 1 ] = 1 ; for ( int i = 2 ; i <= MAX ; i ++ ) { int mspf = spf [ i ] ; int prim = mspf ; int temp = i ; int cnt = 0 ; while ( temp % mspf == 0 ) { temp /= mspf ; cnt += 1 ; prim = prim * mspf ; } tfactor [ i ] = ( cnt + 1 ) * tfactor [ temp ] ; pre [ i ] = pre [ i - 1 ] + tfactor [ i ] ; } } static int BinarySearch ( int X ) { int start = 1 ; int end = MAX - 1 ; while ( start < end ) { int mid = ( start + end ) / 2 ; if ( pre [ mid ] == X ) return mid ; else if ( pre [ mid ] < X ) start = mid + 1 ; else end = mid ; } return start ; } static void findSumOfCount ( int X ) { calculate_SPF ( ) ; CountTotalfactors ( ) ; System . out . print ( BinarySearch ( X ) + "NEW_LINE"); } public static void main ( String [ ] args ) { int X = 10 ; findSumOfCount ( X ) ; } }