Count ways to split N! into two distinct co-prime factors

Namachila November 19, 2025

0 4 8 minutes read

Given an integer N, the task is to find the number of ways N! can be split into two distinct factors A and B such that A and B are co-primes. Since the answer can be very large, print it modulo 10⁹ + 7.

Examples:

Input: N = 5
Output: 4
Explanation: The pairs are (1, 120), (3, 40), (5, 24), (8, 15).

Input: N = 7
Output: 8
Explanation: The pairs are (1, 5040), (5, 1008), (7, 720), (9, 560), (16, 315), (35, 144), (45, 112), (63, 80).

Naive Approach: The simplest approach is to calculate the factorial of N! and generate all its factors and check if any pair of factors (i, j) has GCD(i, j) == 1.

Time Complexity: O(?N!)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to find distinct prime factors of N and then count ways to split it into two distinct co-prime factors A & B. Follow the steps below to solve the problem:

Every positive integer can be represented as a product of powers of primes (prime factorization). Therefore, every possible value of N can be expressed as N = 2^p× 3^q× 5^r…..(p ? 0, q ? 0, r ? 0).
Now, the task is to split N into two distinct co-prime factors. This can be done by assigning each of the terms in prime factorization of N into two possible combinations each time.

Illustration:

Let N = 18900.
Expressing N in the form of its prime factors, 18900 = 2²* 3³* 5²* 7¹

Each of 2², 3³, 5² and 7¹ can be assigned to either of the two factors. Using product rule in combinatorics, the total possible ways are 2⁴ = 16. Since the two factors have no order, the total possible ways are 2³ = 8. Therefore, the number of ways N is 2^{X – 1}, where X is the number of prime-factors of N.

Follow the steps below to solve the problem:

The prime factorization of N! contains all primes which are less than or equal to N.
If x is the count of primes less than or equal to N, then the number of ways N! (factorial) can be split into two distinct co-prime factors is equal to 2^{x – 1}.
Precompute the number of primes ? n ? N using Sieve of Eratosthenes and store them in an array.
To calculate the result modulo 10⁹ + 7, use Modular Exponentiation i.e. calculate x^y % p.

Below is the implementation of the above approach:

C++

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Maximum value of N
#define MAXN 1000000
 
// Stores at each indices if
// given number is prime or not
int is_prime[MAXN] = { 0 };
 
// Stores count_of_primes
int count_of_primes[MAXN] = { 0 };
 
// Function to generate primes
// using Sieve of Eratosthenes
void sieve()
{
    for (int i = 3; i < MAXN; i += 2) {
 
        // Assume all odds are primes
        is_prime[i] = 1;
    }
 
    for (int i = 3; i * i < MAXN; i += 2) {
 
        // If a prime is encountered
        if (is_prime[i])
 
            for (int j = i * i; j < MAXN;
                 j += i) {
 
                // Mark all its multiples
                // as non-prime
                is_prime[j] = 0;
            }
    }
 
    is_prime[2] = 1;
 
    // Count primes <= MAXN
    for (int i = 1; i < MAXN; i++)
        count_of_primes[i]
            = count_of_primes[i - 1]
              + is_prime[i];
}
 
// Function to calculate (x ^ y) % p
// in O(log y)
long long int power(long long int x,
                    long long int y,
                    long long int p)
{
    long long result = 1;
    while (y > 0) {
        if (y & 1 == 1)
            result = (result * x) % p;
        x = (x * x) % p;
        y >>= 1;
    }
    return result;
}
 
// Utility function to count the number of ways
// N! can be split into co-prime factors
void numberOfWays(int N)
{
    long long int count
        = count_of_primes[N] - 1;
    long long int mod = 1000000007;
    long long int answer
        = power(2, count, mod);
 
    if (N == 1)
        answer = 0;
 
    cout << answer;
}
 
// Driver Code
int main()
{
    // Calling sieve function
    sieve();
 
    // Given N
    int N = 7;
 
    // Function call
    numberOfWays(N);
 
    return 0;
}

Java

// Java Program for the above approach
import java.util.*;
 
class GFG {
 
    // Maximum value of N
    static final int MAXN = 1000000;
 
    // Stores at each indices if
    // given number is prime or not
    static int is_prime[];
 
    // Stores count_of_primes
    static int count_of_primes[];
 
    // Function to generate primes
    // using Sieve of Eratosthenes
    static void sieve()
    {
        is_prime = new int[MAXN];
        count_of_primes = new int[MAXN];
        Arrays.fill(is_prime, 0);
        Arrays.fill(count_of_primes, 0);
 
        for (int i = 3; i < MAXN; i += 2) {
 
            // Assume all odds are primes
            is_prime[i] = 1;
        }
 
        for (int i = 3; i * i < MAXN; i += 2) {
 
            // If a prime is encountered
            if (is_prime[i] == 1) {
                for (int j = i * i; j < MAXN;
                     j += i) {
                    // MArk all its multiples
                    // as non-prime
                    is_prime[j] = 0;
                }
            }
        }
 
        is_prime[2] = 1;
 
        // Count all primes upto MAXN
        for (int i = 1; i < MAXN; i++)
            count_of_primes[i]
                = count_of_primes[i - 1] + is_prime[i];
    }
 
    // Function to calculate (x ^ y) % p
    // in O(log y)
    static long power(long x, long y, long p)
    {
        long result = 1;
        while (y > 0) {
            if ((y & 1) == 1)
                result = (result * x) % p;
            x = (x * x) % p;
            y >>= 1;
        }
        return result;
    }
 
    // Utility function to count the number of
    // ways N! can be split into two co-prime factors
    static void numberOfWays(int N)
    {
        long count = count_of_primes[N] - 1;
        long mod = 1000000007;
        long answer = power(2, count, mod);
        if (N == 1)
            answer = 0;
        long ans = answer;
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Calling sieve function
        sieve();
 
        // Given N
        int N = 7;
 
        // Function call
        numberOfWays(N);
    }
}

Python3

# Python3 program for the above approach
import math
 
# Maximum value of N
MAXN = 1000000
 
# Stores at each indices if
# given number is prime or not
is_prime = [0] * MAXN
 
# Stores count_of_primes
count_of_primes = [0] * MAXN
 
# Function to generate primes
# using Sieve of Eratosthenes
def sieve():
     
    for i in range(3, MAXN, 2):
         
        # Assume all odds are primes
        is_prime[i] = 1
 
    for i in range(3, int(math.sqrt(MAXN)), 2):
 
        # If a prime is encountered
        if is_prime[i]:
            for j in range(i * i, MAXN, i):
 
                # Mark all its multiples
                # as non-prime
                is_prime[j] = 0
 
    is_prime[2] = 1
 
    # Count primes <= MAXN
    for i in range(1, MAXN):
        count_of_primes[i] = (count_of_primes[i - 1] +
                                     is_prime[i])
 
# Function to calculate (x ^ y) % p
# in O(log y)
def power(x, y, p):
   
    result = 1
    while (y > 0):
        if y & 1 == 1:
            result = (result * x) % p
             
        x = (x * x) % p
        y >>= 1
 
    return result
 
# Utility function to count the number of ways
# N! can be split into co-prime factors
def numberOfWays(N):
   
    count = count_of_primes[N] - 1
    mod = 1000000007
    answer = power(2, count, mod)
 
    if N == 1:
        answer = 0
 
    print(answer)
 
# Driver Code
if __name__ == "__main__":
   
    # Calling sieve function
    sieve()
 
    # Given N
    N = 7
 
    # Function call
    numberOfWays(N)
 
# This code is contributed by akhilsaini

C#

// C# program for the above approach 
using System;
 
class GFG{
 
// Maximum value of N
static int MAXN = 1000000;
 
// Stores at each indices if
// given number is prime or not
static int[] is_prime;
 
// Stores count_of_primes
static int[] count_of_primes;
 
// Function to generate primes
// using Sieve of Eratosthenes
static void sieve()
{
    is_prime = new int[MAXN];
    count_of_primes = new int[MAXN];
    Array.Fill(is_prime, 0);
    Array.Fill(count_of_primes, 0);
 
    for(int i = 3; i < MAXN; i += 2) 
    {
         
        // Assume all odds are primes
        is_prime[i] = 1;
    }
 
    for(int i = 3; i * i < MAXN; i += 2) 
    {
         
        // If a prime is encountered
        if (is_prime[i] == 1) 
        {
            for(int j = i * i; j < MAXN; j += i)
            {
                 
                // MArk all its multiples
                // as non-prime
                is_prime[j] = 0;
            }
        }
    }
 
    is_prime[2] = 1;
 
    // Count all primes upto MAXN
    for(int i = 1; i < MAXN; i++)
        count_of_primes[i] = count_of_primes[i - 1] +
                                    is_prime[i];
}
 
// Function to calculate (x ^ y) % p
// in O(log y)
static long power(long x, long y, long p)
{
    long result = 1;
    while (y > 0)
    {
        if ((y & 1) == 1)
            result = (result * x) % p;
             
        x = (x * x) % p;
        y >>= 1;
    }
    return result;
}
 
// Utility function to count the number of
// ways N! can be split into two co-prime factors
static void numberOfWays(int N)
{
    long count = count_of_primes[N] - 1;
    long mod = 1000000007;
    long answer = power(2, count, mod);
     
    if (N == 1)
        answer = 0;
         
    long ans = answer;
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
     
    // Calling sieve function
    sieve();
 
    // Given N
    int N = 7;
 
    // Function call
    numberOfWays(N);
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// Javascript Program for the above approach
 
// Maximum value of N
var MAXN = 1000000
 
// Stores at each indices if
// given number is prime or not
var is_prime = Array(MAXN).fill(0);
 
// Stores count_of_primes
var count_of_primes = Array(MAXN).fill(0);
 
// Function to generate primes
// using Sieve of Eratosthenes
function sieve()
{
    for (var i = 3; i < MAXN; i += 2) {
 
        // Assume all odds are primes
        is_prime[i] = 1;
    }
 
    for (var i = 3; i * i < MAXN; i += 2) {
 
        // If a prime is encountered
        if (is_prime[i])
 
            for (var j = i * i; j < MAXN;
                 j += i) {
 
                // Mark all its multiples
                // as non-prime
                is_prime[j] = 0;
            }
    }
 
    is_prime[2] = 1;
 
    // Count primes <= MAXN
    for (var i = 1; i < MAXN; i++)
        count_of_primes[i]
            = count_of_primes[i - 1]
              + is_prime[i];
}
 
// Function to calculate (x ^ y) % p
// in O(log y)
function power(x, y, p)
{
    var result = 1;
    while (y > 0) {
        if (y & 1 == 1)
            result = (result * x) % p;
        x = (x * x) % p;
        y >>= 1;
    }
    return result;
}
 
// Utility function to count the number of ways
// N! can be split into co-prime factors
function numberOfWays(N)
{
    var count
        = count_of_primes[N] - 1;
    var mod = 1000000007;
    var answer
        = power(2, count, mod);
 
    if (N == 1)
        answer = 0;
 
    document.write( answer);
}
 
// Driver Code
// Calling sieve function
sieve();
// Given N
var N = 7;
// Function call
numberOfWays(N);
 
</script>

Output:

Time Complexity: O(log(log(N)) + log(N))
Auxiliary Space: O(N)

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!