# Find whether n! is divisible by sum of first n natural integers or not in C++

Given an integer value n. Product of first n natural integers or n! (factorial of n )is denoted by P and the sum of first n consecutive natural integers is denoted by S. If S is a factor of P, then print YES, otherwise print NO.

##### Example

n=1, p=1, s=1 –> P is divisible by S so, YES

n=2, p=1*2=2 , s=1+2=3 –>P is not divisible by S so, NO

n=3, p=1*2*3=6, s=1+2+3 –>P is divisible by S so, YES

n=4, p=1*2*3*4=24, s=1+2+3+4=10 –>P is not divisible by S so, NO

##### Wrong approach

If you think you can simply calculate S and P and check if S divides P or not, then think a little more about calculating n! for large values. You will get* integer overflow *if you try to calculate P i.e., n! for a large value of n.

##### Right approach

We know from mathematics that formula for calculating sum of first n consecutive natural integers is:

S = ( n * (n+1) )/2

P = n! = 1*2*3*4*………..*(n-1)*n.

After dividing P by S;

P/s = (1*2* …….. *(n-1)*n) / (( n * (n+1) )/2)

Then canceling out n from numerator and denominator ;

P/S = (1*2* …….. *(n-1)) / ((n+1)/2)

Now we can carefully analyze denominator (n+1)/2;

- We can easily see that if n is an odd integer then n+1 is obviously an even integer. If n+1 is even then it will be easily canceled out by 2 in its denominator and it will be reduced to a value that is between 1 and n-1 so, we can easily cancel them out from numerator and denominator both, and hence P will be divisible by S. So our
*first conclusion*can be drawn from here that*whenever n is odd then P is divisible by S.*

Example for n=5 ; P/S = (1*2*3*4*5)/((5*(5+1))/2)

P/S = (1*2*3*4)/(6/2)

P/S = (1*2*3*4)/3

P/S = 1*2*4 = 8

- Let’s consider the case now when n is even, n+1 will obviously be odd. There can be 2 possibilities when n+1 is odd;

- When n+1 is an odd prime integer, then it is never possible to cancel out n+1 in the denominator because the maximum value of integer present in the numerator is n-1. So, the
*second conclusion*can be drawn from here that**whenever n is even and n+1 is odd prime then P is not divisible by S.** - The second possibility of n being even is that when n+1 is an odd composite. In this case, there must be some odd factor of n+1 present in the numerator within range 3 to n-1, so eventually, n+1 will get canceled out from the denominator. So, we can draw our
*third conclusion*from this case that*whenever n is even and n+1 is odd composite then P is divisible by S.*

Example for n being even and n+1 being odd prime ;

n = 6 –> n+1=7 *here *n+1 is odd prime so, P/S = (1*2*3*4*5*6)/((6*7)/2)

P/S = (1*2*3*4*5*2)/7

we can easily observe that 7 in the denominator will never get canceled out, so P is not divisible by S.

Example for n being even and n+1 being odd composite ;

n = 8 –> n+1=9 *here *n+1 is odd composite so, P/S = (1*2*3*4*5*6*7*8)/((8*9)/2)

P/S = (1*2*3*4*5*6*7*2)/9

P/S = 1*2*4*5*2*7*2 = 1120

so P is not divisible by S.

*Now let’s code all of these conclusions in C++.*

#include<bits/stdc++.h> using namespace std; string solve(int n) { string ans="NO"; if(n%2) { ans="YES"; } else { long long int i=2; for(;i*i<=n+1; i++) { if((n+1)%i==0) { ans="YES"; break; } } } return ans; } int main() { int n; cin>>n; cout<<solve(n); return 0; }

* If you think that this article has added any value to your algorithmic knowledge, then please share your valuable feedback in the comment section. Thank you!*

## Leave a Reply