Comprobar si el producto de los primeros N números naturales es divisible por su suma

Dado un número entero N , la tarea es verificar si el producto de los primeros N números naturales es divisible por la suma de los primeros N números naturales.
Ejemplos: 
 

Entrada: N = 3 
Salida: Sí 
Producto = 1 * 2 * 3 = 6 
Suma = 1 + 2 + 3 = 6
Entrada: N = 6 
Salida: No 
 

Enfoque ingenuo: encuentre la suma y el producto de los primeros N números naturales y verifique si el producto es divisible por la suma.
Enfoque eficiente: ¡ Sabemos que la suma y el producto de los primeros N naturales son suma = (N * (N + 1)) / 2 y producto = N! respectivamente. Ahora, para verificar si el producto es divisible por la suma, debemos verificar si el resto de la siguiente ecuación es 0 o no. 
 

¡NORTE! / (N *(N + 1) / 2)  
2 * (N – 1)! / N + 1 
, es decir, cada factor de (N + 1) debe estar en (2 * (N – 1)!) . Entonces, si (N + 1) es un número primo, entonces estamos seguros de que el producto no es divisible por la suma. 
Entonces, en última instancia, solo verifique si (N + 1) es primo o no. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// 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 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.

# 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# 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 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
?>

<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>

No

Complejidad de tiempo: O(sqrt(n))
Espacio auxiliar: O(1)