Given an integer N, the task is to check whether the product of first N natural numbers is divisible by the sum of first N natural numbers.

Examples:

Input: N = 3
Output: Yes
Product = 1 * 2 * 3 = 6
Sum = 1 + 2 + 3 = 6

Input: N = 6
Output: No

Naive Approach: Find the sum and product of first N natural numbers and check whether the product is divisible by the sum.

Efficient Approach: We know that the sum and product of first N naturals are sum = (N * (N + 1)) / 2 and product = N! respectively. Now to check whether the product is divisible by the sum, we need to check if the remainder of the following equation is 0 or not.

N! / (N *(N + 1) / 2)
2 * (N – 1)! / N + 1
i.e. every factor of (N + 1) should be in (2 * (N – 1)!). So, if (N + 1) is a prime then we are sure that the product is not divisible by the sum.
So ultimately just check if (N + 1) is prime or not.

Below is the implementation of the above approach:

#include <bits/stdc++.h>

using namespace std;

  

bool isPrime(int n)

{

    

    if (n <= 1)

        return false;

    if (n <= 3)

        return true;

  

    

    

    if (n % 2 == 0 || n % 3 == 0)

        return false;

  

    for (int i = 5; i * i <= n; i = i + 6)

        if (n % i == 0 || n % (i + 2) == 0)

            return false;

  

    return true;

}

  

bool isDivisible(int n)

{

    if (isPrime(n + 1))

        return false;

    return true;

}

  

int main()

{

    int n = 6;

    if (isDivisible(n))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}



If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.