Minimise N such that sum of count of all factors upto N is greater than or equal to X

0 0 14 minutes read

Given a number X, the task is to find the minimum number N such that the sum of the count of all factors from 1 to N is greater than equal to X.
Examples:

Input: X = 10
Output: 5
Explanation:
Total factors of 1 = 1 (1)
Total factors of 2 = 2 (1, 2)
Total factors of 3 = 2 (1, 3)
Total factors of 4 = 3 (1, 2, 4)
Total factors of 5 = 2 (1, 5)
Total count = 1 + 2 + 2 + 3 + 2 = 10 which is greater than or equal to X i.e., 10
Input: X = 19
Output: 8
Explanation:
Total factors of 1 = 1 (1)
Total factors of 2 = 2 (1, 2)
Total factors of 3 = 2 (1, 3)
Total factors of 4 = 3 (1, 2, 4)
Total factors of 5 = 2 (1, 5)
Total factors of 6 = 2 (1, 2, 3, 6)
Total factors of 7 = 2 (1, 7)
Total factors of 8 = 2 (1, 2, 4, 8)
Total count = 1 + 2 + 2 + 3 + 2 + 4 + 2 + 4 = 20 which is greater than or equal to X i.e., 19

Naive Approach: The naive approach is to run a loop starting from 1 until the total count of factor is greater than equal to X.

Algorithm:

Define a macro MAX as 1000050 and a type alias ‘lli’ for long int.
Define a function CountFactors that takes a long integer ‘N’ as input and returns the count of total factors of ‘N’.
Inside the CountFactors function, initialize a variable ‘cnt’ to zero.
Run a loop from i=1 to i*i <= N and check if N is divisible by i without leaving a remainder. If yes, increment cnt by 1. If N/i is not equal to i, increment cnt by 1 again.
Return the value of cnt as the count of total factors of N.
Define another function minN that takes a long integer ‘X’ as input and returns the lowest number ‘N’ for which the sum of total factors of all numbers from 1 to N is greater than or equal to X.
Inside the minN function, initialize a variable ‘i’ to 1 and a variable ‘total’ to 0.
Run a loop until a condition is met that will break the loop. Inside the loop, add the count of total factors of ‘i’ returned by CountFactors function to the variable ‘total’.
If ‘total’ is greater than or equal to ‘X’, return the current value of ‘i’ as the lowest number ‘N’ satisfying the given condition.
If ‘total’ is less than ‘X’, increment ‘i’ by 1 and continue with the loop until the condition is met.
In the main function, define a long integer ‘X’ and initialize it to 10.
Call the minN function with ‘X’ as input and print the returned value.
End the program.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1000050
#define lli long int
 
// Function to count total factors of N
lli CountFactors(lli N)
{
    lli cnt = 0;
    for (lli i = 1;
         i * i <= N; i++) {
 
        if (N % i == 0)
            cnt += ((N / i == i) ? 1 : 2);
    }
 
    // Return the count
    return cnt;
}
 
// Function to search lowest N
// such that the given condition
// is satisfied
lli minN(lli X)
{
    lli i = 1;
    lli total = 0;
 
    while (1) {
 
        // Add the count of total factor
        // of i to variable total
        total = total + CountFactors(i);
 
        // If total count is greater than
        // equal to N, then return i
        if (total >= X)
            return i;
        i++;
    }
}
 
// Driver Code
int main()
{
    // Given sum
    lli X = 10;
 
    // Function Call
    cout << minN(X) << endl;
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
static final int MAX = 1000050;
 
// Function to count total factors of N
static int CountFactors(int N)
{
    int cnt = 0;
    for(int i = 1; i * i <= N; i++) 
    {
       if (N % i == 0)
           cnt += ((N / i == i) ? 1 : 2);
    }
 
    // Return the count
    return cnt;
}
 
// Function to search lowest N
// such that the given condition
// is satisfied
static int minN(int X)
{
    int i = 1;
    int total = 0;
 
    while (true)
    {
         
        // Add the count of total factor
        // of i to variable total
        total = total + CountFactors(i);
 
        // If total count is greater than
        // equal to N, then return i
        if (total >= X)
            return i;
        i++;
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given sum
    int X = 10;
 
    // Function Call
    System.out.print(minN(X) + "\n");
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program for 
# the above approach
MAX = 1000050
 
# Function to count 
# total factors of N
def CountFactors(N):
 
    cnt = 0
    i = 1
    while i * i <= N:
 
        if (N % i == 0):
            if (N // i == i):
                cnt +=  1
            else:
                cnt +=  2
        i += 1  
 
    # Return the count
    return cnt
 
# Function to search lowest N
# such that the given condition
# is satisfied
def minN(X):
 
    i = 1
    total = 0
 
    while (1):
 
        # Add the count of total factor
        # of i to variable total
        total = total + CountFactors(i)
 
        # If total count is greater than
        # equal to N, then return i
        if (total >= X):
            return i
        i += 1
 
# Driver Code
if __name__ == "__main__":
 
    # Given sum
    X = 10
 
    # Function Call
    print( minN(X))
 
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
  
//static readonly int MAX = 1000050;
  
// Function to count total factors of N
static int CountFactors(int N)
{
    int cnt = 0;
    for(int i = 1; i * i <= N; i++) 
    {
       if (N % i == 0)
           cnt += ((N / i == i) ? 1 : 2);
    }
  
    // Return the count
    return cnt;
}
  
// Function to search lowest N
// such that the given condition
// is satisfied
static int minN(int X)
{
    int i = 1;
    int total = 0;
  
    while (true)
    {
          
        // Add the count of total factor
        // of i to variable total
        total = total + CountFactors(i);
  
        // If total count is greater than
        // equal to N, then return i
        if (total >= X)
            return i;
        i++;
    }
}
  
// Driver Code
public static void Main(String[] args)
{
      
    // Given sum
    int X = 10;
  
    // Function Call
    Console.Write(minN(X) + "\n");
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// javascript program for the above approachstatic final var MAX = 1000050;
 
// Function to count total factors of N
function CountFactors(N)
{
    var cnt = 0;
    for(i = 1; i * i <= N; i++) 
    {
       if (N % i == 0)
           cnt += ((N / i == i) ? 1 : 2);
    }
 
    // Return the count
    return cnt;
}
 
// Function to search lowest N
// such that the given condition
// is satisfied
function minN(X)
{
    var i = 1;
    var total = 0;
 
    while (true)
    {
         
        // Add the count of total factor
        // of i to variable total
        total = total + CountFactors(i);
 
        // If total count is greater than
        // equal to N, then return i
        if (total >= X)
            return i;
        i++;
    }
}
 
// Driver Code
//Given sum
var X = 10;
 
// Function Call
document.write(minN(X) + "\n");
 
// This code is contributed by 29AjayKumar 
</script>

Output:

Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by doing some precomputation. Below are the steps:

Calculate and store the smallest prime factor of each number (SPF) using the approach discussed in this article.
Find the count of factors of N efficiently, using Sieve of Eratosthenes and the above calculated smallest prime factor.
Create a prefix sum array to store the sum of the count of factors from 1 to MAX.
To find the lowest N such that the above condition satisfied, instead of linear search in prefix array perform a binary search on the prefix sum array (as the prefix sum array will be in increasing order), so that time complexity will be optimal for multiple queries also.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1000050
#define lli long int
 
// Array to store smallest
// prime factors of each no.
lli spf[MAX + 1];
 
// Function to calculate smallest
// prime factor of N.
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)
 
                // marking spf[j] if
                // it is not previously
                // marked
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
 
// Array to store the count of
// factor for N
lli tfactor[MAX + 1];
 
// Prefix array which contains
// the count of factors from 1 to N
lli pre[MAX + 1];
 
// Function to count total factors
// from 1 to N
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;
        }
 
        // Store total factors of i
        tfactor[i] = (cnt + 1)
                     * tfactor[temp];
 
        // Stores total factors
        // from 1 to i
        pre[i] = pre[i - 1]
                 + tfactor[i];
    }
}
 
// Function to search lowest X
// such that the given condition
// is satisfied
lli BinarySearch(lli X)
{
    lli start = 1;
    lli end = MAX - 1;
 
    while (start < end) {
 
        // Find mid
        lli mid = (start + end) / 2;
 
        if (pre[mid] == X)
            return mid;
 
        // Search in the right half
        else if (pre[mid] < X)
            start = mid + 1;
 
        // Search in the left half
        else
            end = mid;
    }
 
    // Return the position after
    // Binary Search
    return start;
}
 
// Function to find the required sum
void findSumOfCount(int X)
{
 
    // Precompute smallest prime
    // factor of each value
    calculate_SPF();
 
    // Calculate count of total
    // factors from 1 to N
    CountTotalfactors();
 
    // Binary search to find minimum N
    cout << BinarySearch(X)
         << endl;
}
 
// Driver Code
int main()
{
    // Given Sum
    int X = 10;
 
    // Function Call
    findSumOfCount(X);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static final int MAX = 1000050;
 
// Array to store smallest
// prime factors of each no.
static int []spf = new int[MAX + 1];
 
// Function to calculate smallest
// prime factor of N.
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)
            
              // marking spf[j] if
              // it is not previously
              // marked
              if (spf[j] == j)
                  spf[j] = i;
       }
    }
}
 
// Array to store the count of
// factor for N
static int []tfactor = new int[MAX + 1];
 
// Prefix array which contains
// the count of factors from 1 to N
static int []pre = new int[MAX + 1];
 
// Function to count total factors
// from 1 to N
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;
       }
        
       // Store total factors of i
       tfactor[i] = (cnt + 1) * tfactor[temp];
        
       // Stores total factors
       // from 1 to i
       pre[i] = pre[i - 1] + tfactor[i];
    }
}
 
// Function to search lowest X
// such that the given condition
// is satisfied
static int BinarySearch(int X)
{
    int start = 1;
    int end = MAX - 1;
 
    while (start < end)
    {
         
        // Find mid
        int mid = (start + end) / 2;
 
        if (pre[mid] == X)
            return mid;
 
        // Search in the right half
        else if (pre[mid] < X)
            start = mid + 1;
 
        // Search in the left half
        else
            end = mid;
    }
 
    // Return the position after
    // Binary Search
    return start;
}
 
// Function to find the required sum
static void findSumOfCount(int X)
{
 
    // Precompute smallest prime
    // factor of each value
    calculate_SPF();
 
    // Calculate count of total
    // factors from 1 to N
    CountTotalfactors();
 
    // Binary search to find minimum N
    System.out.print(BinarySearch(X) + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Sum
    int X = 10;
 
    // Function Call
    findSumOfCount(X);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

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

C#

// C# program for the above approach
using System;
class GFG{
 
const int MAX = 1000050;
 
// Array to store smallest
// prime factors of each no.
static int []spf = new int[MAX + 1];
 
// Function to calculate smallest
// prime factor of N.
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)
                 
                // marking spf[j] if
                // it is not previously
                // marked
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
 
// Array to store the count of
// factor for N
static int []tfactor = new int[MAX + 1];
 
// Prefix array which contains
// the count of factors from 1 to N
static int []pre = new int[MAX + 1];
 
// Function to count total factors
// from 1 to N
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;
        }
             
        // Store total factors of i
        tfactor[i] = (cnt + 1) * tfactor[temp];
             
        // Stores total factors
        // from 1 to i
        pre[i] = pre[i - 1] + tfactor[i];
    }
}
 
// Function to search lowest X
// such that the given condition
// is satisfied
static int BinarySearch(int X)
{
    int start = 1;
    int end = MAX - 1;
 
    while (start < end)
    {
         
        // Find mid
        int mid = (start + end) / 2;
 
        if (pre[mid] == X)
            return mid;
 
        // Search in the right half
        else if (pre[mid] < X)
            start = mid + 1;
 
        // Search in the left half
        else
            end = mid;
    }
 
    // Return the position after
    // Binary Search
    return start;
}
 
// Function to find the required sum
static void findSumOfCount(int X)
{
 
    // Precompute smallest prime
    // factor of each value
    calculate_SPF();
 
    // Calculate count of total
    // factors from 1 to N
    CountTotalfactors();
 
    // Binary search to find minimum N
    Console.Write(BinarySearch(X) + "\n");
}
 
// Driver Code
public static void Main()
{
     
    // Given Sum
    int X = 10;
 
    // Function Call
    findSumOfCount(X);
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
 
// JavaScript program for the above approach
 
var MAX = 1000050;
 
// Array to store smallest
// prime factors of each no.
var spf = Array(MAX+1);
 
// Function to calculate smallest
// prime factor of N.
function calculate_SPF()
{
    for (var i = 0; i <= MAX; i++)
        spf[i] = i;
 
    for (var i = 4; i <= MAX; i += 2)
        spf[i] = 2;
 
    for (var i = 3;
         i * i <= MAX; i++) {
 
        if (spf[i] == i) {
            for (var j = i * i;
                 j <= MAX; j += i)
 
                // marking spf[j] if
                // it is not previously
                // marked
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
 
// Array to store the count of
// factor for N
var tfactor = Array(MAX+1);
 
// Prefix array which contains
// the count of factors from 1 to N
var pre = Array(MAX+1);
 
// Function to count total factors
// from 1 to N
function CountTotalfactors()
{
    tfactor[1] = pre[1] = 1;
 
    for (var i = 2; i <= MAX; i++) {
 
        var mspf = spf[i];
        var prim = mspf;
        var temp = i;
        var cnt = 0;
 
        while (temp % mspf == 0) {
            temp = parseInt(temp/mspf);
            cnt += 1;
            prim = prim * mspf;
        }
 
        // Store total factors of i
        tfactor[i] = (cnt + 1)
                     * tfactor[temp];
 
        // Stores total factors
        // from 1 to i
        pre[i] = pre[i - 1]
                 + tfactor[i];
    }
}
 
// Function to search lowest X
// such that the given condition
// is satisfied
function BinarySearch(X)
{
    var start = 1;
    var end = MAX - 1;
 
    while (start < end) {
 
        // Find mid
        var mid = parseInt((start + end) / 2);
 
        if (pre[mid] == X)
            return mid;
 
        // Search in the right half
        else if (pre[mid] < X)
            start = mid + 1;
 
        // Search in the left half
        else
            end = mid;
    }
 
    // Return the position after
    // Binary Search
    return start;
}
 
// Function to find the required sum
function findSumOfCount( X)
{
 
    // Precompute smallest prime
    // factor of each value
    calculate_SPF();
 
    // Calculate count of total
    // factors from 1 to N
    CountTotalfactors();
 
    // Binary search to find minimum N
    document.write( BinarySearch(X) + "<br>");
}
 
// Driver Code
 
// Given Sum
var X = 10;
 
// Function Call
findSumOfCount(X);
 
</script>

Output:

Time Complexity: O(MAX*log(MAX))
Auxiliary Space: O(MAX)
Note: If there are Q queries, then the time complexity of finding N for all the Q queries will be O(Q*log(MAX)).

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!