Comprueba si el factorial de N es divisible por la suma de los cuadrados de los primeros N números naturales

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es encontrar si fact(N) es divisible por sum(N) donde fact(N) es el factorial de N y sum(N) = 1 2 + 2 2 + 3 2 + … + N 2 .
Ejemplos: 
 

Entrada: N = 5 
Salida: No 
fact(N) = 120, sum(N) = 55 
Y, 120 no es divisible por 55
Entrada: N = 7 
Salida: Sí 
 

Acercarse: 
 

  1. Aquí es importante darse cuenta primero de la fórmula cerrada para la suma de los cuadrados de todos los números. Suma de cuadrados de primeros N números naturales .
  2. Ahora, dado que n es un factor común tanto de N factorial como de la suma, podemos eliminarlo.
  3. Ahora, para cada primo P en Valor (N + 1) * (2N + 1), digamos que hay X factores de P en Valor y luego encuentre el número de factores de P en Factorial (N – 1), digamos que son Y. Si Y < X, entonces dos nunca son divisibles, de lo contrario continúa.
  4. Para calcular el número de factores de P en factorial (N), simplemente podemos usar la fórmula de Lengendre .
  5. En el punto 4, aumenta la cuenta del Número primo 2, 3 con 1 para dar cuenta del 6 en la fórmula de sumatoria.
  6. Verifique individualmente todos los primos P en Valor, y si todos satisfacen la condición 3, entonces la respuesta es Sí.
  7. El punto 2 nos ayudará a reducir nuestra complejidad temporal con un factor de N.

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

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>
Producción: 

No

 

Complejidad de tiempo: O (nlogn)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por krikti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *