# Check if product of first N natural numbers is divisible by their sum

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 = 3Output:Yes

Product = 1 * 2 * 3 = 6

Sum = 1 + 2 + 3 = 6Input:N = 6Output: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:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function that returns true if n is prime` `bool` `isPrime(` `int` `n)` `{` ` ` `// Corner cases` ` ` `if` `(n <= 1)` ` ` `return` `false` `;` ` ` `if` `(n <= 3)` ` ` `return` `true` `;` ` ` `// This is checked so that we can skip` ` ` `// middle five numbers in below loop` ` ` `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` `;` `}` `// Function that return true if the product` `// of the first n natural numbers is divisible` `// by the sum of first n natural numbers` `bool` `isDivisible(` `int` `n)` `{` ` ` `if` `(isPrime(n + 1))` ` ` `return` `false` `;` ` ` `return` `true` `;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 6;` ` ` `if` `(isDivisible(n))` ` ` `cout << ` `"Yes"` `;` ` ` `else` ` ` `cout << ` `"No"` `;` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `class` `GFG` `{` ` ` `// Function that returns true if n is prime` `static` `boolean` `isPrime(` `int` `n)` `{` ` ` `// Corner cases` ` ` `if` `(n <= ` `1` `)` ` ` `return` `false` `;` ` ` `if` `(n <= ` `3` `)` ` ` `return` `true` `;` ` ` `// This is checked so that we can skip` ` ` `// middle five numbers in below loop` ` ` `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` `;` `}` `// Function that return true if the product` `// of the first n natural numbers is divisible` `// by the sum of first n natural numbers` `static` `boolean` `isDivisible(` `int` `n)` `{` ` ` `if` `(isPrime(n + ` `1` `))` ` ` `return` `false` `;` ` ` `return` `true` `;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `n = ` `6` `;` ` ` `if` `(isDivisible(n))` ` ` `System.out.println(` `"Yes"` `);` ` ` `else` ` ` `System.out.println(` `"No"` `);` `}` `}` `// This code is contributed by Code_Mech.` |

## Python3

`# Python 3 implementation of the approach` `from` `math ` `import` `sqrt` `# Function that returns true if n is prime` `def` `isPrime(n):` ` ` ` ` `# Corner cases` ` ` `if` `(n <` `=` `1` `):` ` ` `return` `False` ` ` `if` `(n <` `=` `3` `):` ` ` `return` `True` ` ` `# This is checked so that we can skip` ` ` `# middle five numbers in below loop` ` ` `if` `(n ` `%` `2` `=` `=` `0` `or` `n ` `%` `3` `=` `=` `0` `):` ` ` `return` `False` ` ` `for` `i ` `in` `range` `(` `5` `, ` `int` `(sqrt(n)) ` `+` `1` `, ` `6` `):` ` ` `if` `(n ` `%` `i ` `=` `=` `0` `or` `n ` `%` `(i ` `+` `2` `) ` `=` `=` `0` `):` ` ` `return` `False` ` ` `return` `True` `# Function that return true if the product` `# of the first n natural numbers is divisible` `# by the sum of first n natural numbers` `def` `isDivisible(n):` ` ` `if` `(isPrime(n ` `+` `1` `)):` ` ` `return` `False` ` ` `return` `True` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `n ` `=` `6` ` ` `if` `(isDivisible(n)):` ` ` `print` `(` `"Yes"` `)` ` ` `else` `:` ` ` `print` `(` `"No"` `)` `# This code is contributed by` `# Surendra_Gangwar` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` ` ` `// Function that returns true if n is prime` `static` `bool` `isPrime(` `int` `n)` `{` ` ` `// Corner cases` ` ` `if` `(n <= 1)` ` ` `return` `false` `;` ` ` `if` `(n <= 3)` ` ` `return` `true` `;` ` ` `// This is checked so that we can skip` ` ` `// middle five numbers in below loop` ` ` `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` `;` `}` `// Function that return true if the product` `// of the first n natural numbers is divisible` `// by the sum of first n natural numbers` `static` `bool` `isDivisible(` `int` `n)` `{` ` ` `if` `(isPrime(n + 1))` ` ` `return` `false` `;` ` ` `return` `true` `;` `}` `// Driver code` `static` `void` `Main()` `{` ` ` `int` `n = 6;` ` ` `if` `(isDivisible(n))` ` ` `Console.WriteLine(` `"Yes"` `);` ` ` `else` ` ` `Console.WriteLine(` `"No"` `);` `}` `}` `// This code is contributed by mits` |

## PHP

`<?php` `// PHP implementation of the approach` `// Function that returns true if n is prime` `function` `isPrime(` `$n` `)` `{` ` ` `// Corner cases` ` ` `if` `(` `$n` `<= 1)` ` ` `return` `false;` ` ` `if` `(` `$n` `<= 3)` ` ` `return` `true;` ` ` `// This is checked so that we can skip` ` ` `// middle five numbers in below loop` ` ` `if` `(` `$n` `% 2 == 0 || ` `$n` `% 3 == 0)` ` ` `return` `false;` ` ` `for` `(` `$i` `= 5; ` `$i` `* ` `$i` `<= ` `$n` `; ` `$i` `= ` `$i` `+ 6)` ` ` `if` `(` `$n` `% ` `$i` `== 0 || ` `$n` `% (` `$i` `+ 2) == 0)` ` ` `return` `false;` ` ` `return` `true;` `}` `// Function that return true if the product` `// of the first n natural numbers is divisible` `// by the sum of first n natural numbers` `function` `isDivisible(` `$n` `)` `{` ` ` `if` `(isPrime(` `$n` `+ 1))` ` ` `return` `false;` ` ` `return` `true;` `}` `// Driver code` `$n` `= 6;` `if` `(isDivisible(` `$n` `))` ` ` `echo` `"Yes"` `;` `else` ` ` `echo` `"No"` `;` `// This code is contributed by Akanksha Rai` `?>` |

## Javascript

`<script>` `// javascript implementation of the approach` `// Function that returns true if n is prime` `function` `isPrime(n)` `{` ` ` `// Corner cases` ` ` `if` `(n <= 1)` ` ` `return` `false` `;` ` ` `if` `(n <= 3)` ` ` `return` `true` `;` ` ` `// This is checked so that we can skip` ` ` `// middle five numbers in below loop` ` ` `if` `(n % 2 == 0 || n % 3 == 0)` ` ` `return` `false` `;` ` ` `for` `(i = 5; i * i <= n; i = i + 6)` ` ` `if` `(n % i == 0 || n % (i + 2) == 0)` ` ` `return` `false` `;` ` ` `return` `true` `;` `}` `// Function that return true if the product` `// of the first n natural numbers is divisible` `// by the sum of first n natural numbers` `function` `isDivisible(n)` `{` ` ` `if` `(isPrime(n + 1))` ` ` `return` `false` `;` ` ` `return` `true` `;` `}` `// Driver code` `var` `n = 6;` `if` `(isDivisible(n))` ` ` `document.write(` `"Yes"` `);` `else` ` ` `document.write(` `"No"` `);` `// This code is contributed by Princi Singh` `</script>` |

**Output:**

No

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.