Minimise N such that sum of count of all factors upto N is greater than or equal to X | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000050 NEW_LINE #define lli  long int NEW_LINE lli spf [ MAX + 1 ] ; void calculate_SPF ( ) { for ( lli i = 0 ; i <= MAX ; i ++ ) spf [ i ] = i ; for ( lli i = 4 ; i <= MAX ; i += 2 ) spf [ i ] = 2 ; for ( lli 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 ; } } } lli tfactor [ MAX + 1 ] ; lli pre [ MAX + 1 ] ; void CountTotalfactors ( ) { tfactor [ 1 ] = pre [ 1 ] = 1 ; for ( lli i = 2 ; i <= MAX ; i ++ ) { lli mspf = spf [ i ] ; lli prim = mspf ; lli temp = i ; lli 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 ] ; } } lli BinarySearch ( lli X ) { lli start = 1 ; lli end = MAX - 1 ; while ( start < end ) { lli mid = ( start + end ) / 2 ; if ( pre [ mid ] == X ) return mid ; else if ( pre [ mid ] < X ) start = mid + 1 ; else end = mid ; } return start ; } void findSumOfCount ( int X ) { calculate_SPF ( ) ; CountTotalfactors ( ) ; cout << BinarySearch ( X ) << endl ; } int main ( ) { int X = 10 ; findSumOfCount ( X ) ; return 0 ; }