Check if factorial of N is divisible by the sum of squares of first N natural numbers

0 0 10 minutes read

Given an integer N, the task is to find whether fact(N) is divisible by sum(N) where fact(N) is the factorial of N and sum(N) = 1² + 2² + 3² + … + N².
Examples:

Input: N = 5
Output: No
fact(N) = 120, sum(N) = 55
And, 120 is not divisible by 55
Input: N = 7
Output: Yes

Approach:

It is important here to first realize the closed formula for summation of squares of all numbers. Summation of Squares of first N natural numbers.
Now since, n is a common factor of both N factorial and summation we can remove it.
Now for every prime P in Value (N + 1) * (2N + 1), say there are X factors of P in Value then, find the number of factors of P in Factorial (N – 1), say they are Y. If Y < X, then two are never divisible, else continue.
To calculate the number of factors of P in factorial (N), we can simply use Lengendre Formula.
In point 4, increase the count of Prime Number 2, 3 with 1 to account for the 6 in the formula of summation.
Check individually for all the prime P in Value, and if all satisfy condition 3, then answer is Yes.
Point 2 will help us to reduce our time complexity with a factor of N.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to count number of times
// prime P divide factorial N
bool checkfact(int N, int countprime, int prime)
{
    int countfact = 0;
    if (prime == 2 || prime == 3)
        countfact++;
    int divide = prime;
 
    // Lengendre Formula
    while (N / divide != 0) {
        countfact += N / divide;
        divide = divide * divide;
    }
 
    if (countfact >= countprime)
        return true;
    else
        return false;
}
 
// Function to find count number of times
// all prime P divide summation
bool check(int N)
{
 
    // Formula for summation of square after removing n
    // and constant 6
    int sumsquares = (N + 1) * (2 * N + 1);
    int countprime = 0;
 
    // Loop to traverse over all prime P which divide
    // summation
    for (int i = 2; i <= sqrt(sumsquares); i++) {
        int flag = 0;
 
        while (sumsquares % i == 0) {
            flag = 1;
            countprime++;
            sumsquares /= i;
        }
 
        if (flag) {
            if (!checkfact(N - 1, countprime, i))
                return false;
            countprime = 0;
        }
    }
 
    // If Number itself is a Prime Number
    if (sumsquares != 1)
        if (!checkfact(N - 1, 1, sumsquares))
            return false;
 
    return true;
}
 
// Driver Code
int main()
{
    int N = 5;
    if (check(N))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach 
class GfG
{ 
 
// Function to count number of times 
// prime P divide factorial N 
static boolean checkfact(int N, int countprime, 
                                    int prime) 
{ 
    int countfact = 0; 
    if (prime == 2 || prime == 3) 
        countfact++; 
    int divide = prime; 
 
    // Lengendre Formula 
    while (N / divide != 0)
    { 
        countfact += N / divide; 
        divide = divide * divide; 
    } 
 
    if (countfact >= countprime) 
        return true; 
    else
        return false; 
} 
 
// Function to find count number of times 
// all prime P divide summation 
static boolean check(int N) 
{ 
 
    // Formula for summation of square after removing n 
    // and constant 6 
    int sumsquares = (N + 1) * (2 * N + 1); 
    int countprime = 0; 
 
    // Loop to traverse over all prime P which divide 
    // summation 
    for (int i = 2; i <= Math.sqrt(sumsquares); i++) 
    { 
        int flag = 0; 
 
        while (sumsquares % i == 0) 
        { 
            flag = 1; 
            countprime++; 
            sumsquares /= i; 
        } 
 
        if (flag == 1) 
        { 
            if (!checkfact(N - 1, countprime, i)) 
                return false; 
            countprime = 0; 
        } 
    } 
 
    // If Number itself is a Prime Number 
    if (sumsquares != 1) 
        if (!checkfact(N - 1, 1, sumsquares)) 
            return false; 
 
    return true; 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
    int N = 5; 
    if (check(N)) 
        System.out.println("Yes"); 
    else
        System.out.println("No"); 
}
} 
 
// This code is contributed by Prerna Saini

Python3

# Python 3 implementation of the approach
from math import sqrt
 
# Function to count number of times
# prime P divide factorial N
def checkfact(N, countprime, prime):
    countfact = 0
    if (prime == 2 or prime == 3):
        countfact += 1
    divide = prime
 
    # Lengendre Formula
    while (int(N / divide ) != 0):
        countfact += int(N / divide)
        divide = divide * divide
 
    if (countfact >= countprime):
        return True
    else:
        return False
 
# Function to find count number of times
# all prime P divide summation
def check(N):
     
    # Formula for summation of square after 
    # removing n and constant 6
    sumsquares = (N + 1) * (2 * N + 1)
    countprime = 0
 
    # Loop to traverse over all prime P 
    # which divide summation
    for i in range(2, int(sqrt(sumsquares)) + 1, 1):
        flag = 0
 
        while (sumsquares % i == 0):
            flag = 1
            countprime += 1
            sumsquares /= i
 
        if (flag):
            if (checkfact(N - 1, 
                countprime, i) == False):
                return False
            countprime = 0
 
    # If Number itself is a Prime Number
    if (sumsquares != 1):
        if (checkfact(N - 1, 1, 
            sumsquares) == False):
            return False
 
    return True
 
# Driver Code
if __name__ == '__main__':
    N = 5
    if(check(N)):
        print("Yes")
    else:
        print("No")
         
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach 
using System;
 
class GFG
{ 
 
// Function to count number of times 
// prime P divide factorial N 
static bool checkfact(int N, int countprime, 
                              int prime) 
{ 
    int countfact = 0; 
    if (prime == 2 || prime == 3) 
        countfact++; 
    int divide = prime; 
 
    // Lengendre Formula 
    while (N / divide != 0)
    { 
        countfact += N / divide; 
        divide = divide * divide; 
    } 
 
    if (countfact >= countprime) 
        return true; 
    else
        return false; 
} 
 
// Function to find count number of times 
// all prime P divide summation 
static bool check(int N) 
{ 
 
    // Formula for summation of square 
    // after removing n and constant 6 
    int sumsquares = (N + 1) * (2 * N + 1); 
    int countprime = 0; 
 
    // Loop to traverse over all prime P 
    // which divide summation 
    for (int i = 2; i <= Math.Sqrt(sumsquares); i++) 
    { 
        int flag = 0; 
 
        while (sumsquares % i == 0) 
        { 
            flag = 1; 
            countprime++; 
            sumsquares /= i; 
        } 
 
        if (flag == 1) 
        { 
            if (!checkfact(N - 1, countprime, i)) 
                return false; 
            countprime = 0; 
        } 
    } 
 
    // If Number itself is a Prime Number 
    if (sumsquares != 1) 
        if (!checkfact(N - 1, 1, sumsquares)) 
            return false; 
 
    return true; 
} 
 
// Driver Code 
public static void Main() 
{ 
    int N = 5; 
    if (check(N)) 
        Console.WriteLine("Yes"); 
    else
        Console.WriteLine("No"); 
}
} 
 
// This code is contributed 
// by Akanksha Rai

PHP

<?php
// PHP implementation of the approach 
 
// Function to count number of times 
// prime P divide factorial N 
function checkfact($N, $countprime, $prime) 
{ 
    $countfact = 0; 
    if ($prime == 2 || $prime == 3) 
        $countfact++; 
    $divide = $prime; 
 
    // Lengendre Formula 
    while ((int)($N / $divide) != 0)
    { 
        $countfact += (int)($N / $divide); 
        $divide = $divide * $divide; 
    } 
 
    if ($countfact >= $countprime) 
        return true; 
    else
        return false; 
} 
 
// Function to find count number of times 
// all prime P divide summation 
function check($N) 
{ 
 
    // Formula for summation of square 
    // after removing n and constant 6 
    $sumsquares = ($N + 1) * (2 * $N + 1); 
    $countprime = 0; 
 
    // Loop to traverse over all prime P 
    // which divide summation 
    for ($i = 2; $i <= sqrt($sumsquares); $i++) 
    { 
        $flag = 0; 
 
        while ($sumsquares % $i == 0) 
        { 
            $flag = 1; 
            $countprime++; 
            $sumsquares = (int)($sumsquares / $i); 
        } 
 
        if ($flag == 1) 
        { 
            if (checkfact($N - 1, $countprime, $i)) 
                return false; 
            $countprime = 0; 
        } 
    } 
 
    // If Number itself is a Prime Number 
    if ($sumsquares != 1) 
        if (checkfact($N - 1, 1, $sumsquares)) 
            return false; 
 
    return true; 
} 
 
// Driver Code 
$N = 5; 
if (check($N)) 
    echo("Yes"); 
else
    echo("No"); 
 
// This code is contributed by Code_Mech
?>

Javascript

<script>
// javascript implementation of the approach 
 
// Function to count number of times 
// prime P divide factorial N 
function checkfact(N , countprime, prime) 
{ 
    var countfact = 0; 
    if (prime == 2 || prime == 3) 
        countfact++; 
    var divide = prime; 
 
    // Lengendre Formula 
    while (N / divide != 0)
    { 
        countfact += N / divide; 
        divide = divide * divide; 
    } 
 
    if (countfact >= countprime) 
        return true; 
    else
        return false; 
} 
 
// Function to find count number of times 
// all prime P divide summation 
function check(N) 
{ 
 
    // Formula for summation of square after removing n 
    // and constant 6 
    var sumsquares = (N + 1) * (2 * N + 1); 
    var countprime = 0; 
 
    // Loop to traverse over all prime P which divide 
    // summation 
    for (i = 2; i <= Math.sqrt(sumsquares); i++) 
    { 
        var flag = 0; 
 
        while (sumsquares % i == 0) 
        { 
            flag = 1; 
            countprime++; 
            sumsquares /= i; 
        } 
 
        if (flag == 1) 
        { 
            if (!checkfact(N - 1, countprime, i)) 
                return false; 
            countprime = 0; 
        } 
    } 
 
    // If Number itself is a Prime Number 
    if (sumsquares != 1) 
        if (!checkfact(N - 1, 1, sumsquares)) 
            return false; 
 
    return true; 
} 
 
// Driver Code 
var N = 5; 
if (check(N)) 
    document.write("Yes"); 
else
    document.write("No"); 
 
// This code is contributed by Princi Singh 
</script>

Output:

No

Time Complexity: O(nlogn)
Auxiliary Space: O(1)

Method 2: Factorial-Sum of Squares Divisibility Test

Approach Steps:

Define a function called is_divisible that takes one argument n.
Calculate the sum of squares of the first n natural numbers using list comprehension and the built-in sum function.
Calculate the factorial of n using a for loop and a variable initialized to 1.
Check if the factorial is divisible by the sum of squares using the modulo operator (%). If the remainder of the division is 0, then the factorial is divisible by the sum of squares.
Call the is_divisible function with a value of n to check if the factorial of n is divisible by the sum of squares of the first n natural numbers.
The function will return True if the factorial of 5 is divisible by the sum of squares of the first 5 natural numbers, or False otherwise.

C++

#include <iostream>
using namespace std;
 
bool is_divisible(int n) {
    // Calculate the sum of squares of the first n natural numbers
    int sum_of_squares = 0;
    for (int i = 1; i <= n; i++) {
        sum_of_squares += i*i;
    }
     
    // Calculate the factorial of n
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial *= i;
    }
     
    // Check if the factorial is divisible by the sum of squares
    if (factorial % sum_of_squares == 0) {
        return true;
    } else {
        return false;
    }
}
 
int main() {
    // Call the function with n = 6
    int n = 6;
    bool result = is_divisible(n);
     
    // Print the result
    cout << "Is the factorial of " << n << " divisible by the sum of squares of the first " << n << " natural numbers? " << (result ? "true" : "false") << endl;
     
    return 0;
}

Java

public class Main {
    public static boolean isDivisible(int n) {
        // Calculate the sum of squares of the first n natural numbers
        int sumOfSquares = 0;
        for (int i = 1; i <= n; i++) {
            sumOfSquares += i * i;
        }
 
        // Calculate the factorial of n
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
        }
 
        // Check if the factorial is divisible by the sum of squares
        if (factorial % sumOfSquares == 0) {
            return true;
        } else {
            return false;
        }
    }
 
    public static void main(String[] args) {
        // Call the function with n = 6
        int n = 6;
        boolean result = isDivisible(n);
 
        // Print the result
        System.out.println("Is the factorial of " + n + " divisible by the sum of squares of the first " + n + " natural numbers? " + (result ? "true" : "false"));
    }
}

Python3

def is_divisible(n):
    # Calculate the sum of squares of the first n natural numbers
    sum_of_squares = sum([i**2 for i in range(1, n+1)])
     
    # Calculate the factorial of n
    factorial = 1
    for i in range(1, n+1):
        factorial *= i
     
    # Check if the factorial is divisible by the sum of squares
    if factorial % sum_of_squares == 0:
        return True
    else:
        return False
 
# Call the function with n = 6
n = 6
result = is_divisible(n)
 
# Print the result
print(f"Is the factorial of {n} divisible by the sum of squares of the first {n} natural numbers? {result}")

C#

using System;
 
class Program {
    static bool IsDivisible(int n)
    {
        // Calculate the sum of squares of the first n
        // natural numbers
        int sumOfSquares = 0;
        for (int i = 1; i <= n; i++) {
            sumOfSquares += i * i;
        }
 
        // Calculate the factorial of n
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            factorial *= i;
        }
 
        // Check if the factorial is divisible by the sum of
        // squares
        if (factorial % sumOfSquares == 0) {
            return true;
        }
        else {
            return false;
        }
    }
 
    static void Main(string[] args)
    {
        // Call the function with n = 6
        int n = 6;
        bool result = IsDivisible(n);
 
        // Print the result
        Console.WriteLine(
            "Is the factorial of " + n
            + " divisible by the sum of squares of the first "
            + n + " natural numbers? "
            + (result ? "true" : "false"));
    }
}

Javascript

function is_divisible(n) {
  // Calculate the sum of squares of the first n natural numbers
  let sum_of_squares = 0;
  for (let i = 1; i <= n; i++) {
    sum_of_squares += i ** 2;
  }
   
  // Calculate the factorial of n
  let factorial = 1;
  for (let i = 1; i <= n; i++) {
    factorial *= i;
  }
   
  // Check if the factorial is divisible by the sum of squares
  if (factorial % sum_of_squares === 0) {
    return true;
  } else {
    return false;
  }
}
 
// Call the function with n = 6
let n = 6;
let result = is_divisible(n);
 
// Print the result
console.log(`Is the factorial of ${n} divisible by the sum of squares of the first ${n} natural numbers? ${result}`);

Output

Is the factorial of 6 divisible by the sum of squares of the first 6 natural numbers? False

The time complexity of the function is O(n).

The auxiliary space of the function is O(1).

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!