Dado un número ‘N’. ¿Comprueba si el factorial de ‘N’ es divisible por la suma de los primeros números naturales ‘N’ o no? Si la divisibilidad es posible, escriba SÍ, de lo contrario, escriba NO.
Ejemplos:
Input: N = 3 Output: YES As (1*2*3)%(1+2+3) = 0, Hence divisibility is possible. Input: N = 4 Output: NO Here (1*2*3*4)%(1+2+3+4) != 0, Hence divisibility doesn't occur.
Acercarse:
- Suma de los primeros ‘n’ números naturales: s = (n)*(n+1)/2 . Esto se puede expresar como (n+1)!/2*(n-1)!
- Ahora n!/s = 2*(n-1)!/(n+1).
- De la fórmula anterior se deriva la observación como:
- Si ‘n+1’ es primo entonces ‘n!’ no es divisible por la suma de los primeros ‘n’ números naturales.
- Si ‘n+1’ no es primo entonces ‘n!’ es divisible por la suma de los primeros ‘n’ números naturales.
Por ejemplo:
- Sea n = 4.
- Por tanto, ‘n!/s’ = 2*(3!)/5. = 1*2*3*2/5 .
- Aquí para n! para ser divisible por ‘s’ necesitamos la presencia de al menos un múltiplo de ‘5’ en el numerador, es decir, en el ejemplo dado, ¡el numerador se expresa como el producto de 3! y 2, para que todo el producto sea divisible por ‘5’,
debe haber al menos un múltiplo de 5, es decir, 5*1 o 5*2 o 5*3 y así sucesivamente. Dado que en el término factorial el número más alto presente es ‘n-1’, el producto, es decir, el numerador nunca puede expresarse con términos de ‘n+1’ si ‘n+1’ es primo. Por lo tanto, la divisibilidad nunca es posible. - En cualquier otro caso, ya sea que ‘n+1’ sea par o impar pero no ‘primo’, la divisibilidad siempre es posible.
Nota: Se debe tener especial cuidado para el caso n=1. como 1! siempre es divisible por 1.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check whether
// a number is prime or not.
bool is_prime(int num)
{
// Count variable to store
// the number of factors of 'num'
int count = 0;
// Counting the number of factors
for (int i = 1; i * i <= (num); i++) {
if ((num) % i == 0) {
if (i * i != (num))
count += 2;
else
count++;
}
}
// If number is prime return true
if (count == 2)
return true;
else
return false;
}
// Function to check for divisibility
string is_divisible(int n)
{
// if 'n' equals 1 then divisibility is possible
if (n == 1) {
return "YES";
}
// Else check whether 'n+1' is prime or not
else {
// If 'n+1' is prime then 'n!' is
// not divisible by 'n*(n+1)/2'
if (is_prime(n + 1))
return "NO";
// else divisibility occurs
else
return "YES";
}
}
// Driver Code
int main()
{
int n;
// Test for n=3
n = 3;
cout << is_divisible(n) << endl;
// Test for n=4
n = 4;
cout << is_divisible(n) << endl;
return 0;
}
Java
class GfG
{
// Function to check whether
// a number is prime or not.
static boolean is_prime(int num)
{
// Count variable to store
// the number of factors of 'num'
int count = 0;
// Counting the number of factors
for (int i = 1; i * i <= (num); i++)
{
if ((num) % i == 0)
{
if (i * i != (num))
count += 2;
else
count++;
}
}
// If number is prime return true
if (count == 2)
return true;
else
return false;
}
// Function to check for divisibility
static String is_divisible(int n)
{
// if 'n' equals 1 then divisibility is possible
if (n == 1)
{
return "YES";
}
// Else check whether 'n+1' is prime or not
else
{
// If 'n+1' is prime then 'n!' is
// not divisible by 'n*(n+1)/2'
if (is_prime(n + 1))
return "NO";
// else divisibility occurs
else
return "YES";
}
}
// Driver Code
public static void main(String[] args)
{
int n;
// Test for n=3
n = 3;
System.out.println(is_divisible(n));
// Test for n=4
n = 4;
System.out.println(is_divisible(n));
}
}
// This code is contributed by Prerna Saini
Python3
# Function to check whether # a number is prime or not. def is_prime(num): # Count variable to store # the number of factors of 'num' count = 0 # Counting the number of factors for i in range(1, num + 1): if i * i > num: break if ((num) % i == 0): if (i * i != (num)): count += 2 else: count += 1 # If number is prime return true if (count == 2): return True else: return False # Function to check for divisibility def is_divisible(n): # if 'n' equals 1 then # divisibility is possible if (n == 1): return "YES" # Else check whether 'n+1' is prime or not else: # If 'n+1' is prime then 'n!' is # not divisible by 'n*(n+1)/2' if (is_prime(n + 1)): return "NO" # else divisibility occurs else: return "YES" # Driver Code # Test for n=3 n = 3 print(is_divisible(n)) # Test for n=4 n = 4 print(is_divisible(n)) # This code is contributed # by mohit kumar
C#
// C# implement the approach
class GfG
{
// Function to check whether
// a number is prime or not.
static bool is_prime(int num)
{
// Count variable to store
// the number of factors of 'num'
int count = 0;
// Counting the number of factors
for (int i = 1; i * i <= (num); i++)
{
if ((num) % i == 0)
{
if (i * i != (num))
count += 2;
else
count++;
}
}
// If number is prime return true
if (count == 2)
return true;
else
return false;
}
// Function to check for divisibility
static string is_divisible(int n)
{
// if 'n' equals 1 then divisibility is possible
if (n == 1)
{
return "YES";
}
// Else check whether 'n+1' is prime or not
else
{
// If 'n+1' is prime then 'n!' is
// not divisible by 'n*(n+1)/2'
if (is_prime(n + 1))
return "NO";
// else divisibility occurs
else
return "YES";
}
}
// Driver Code
static void Main()
{
int n;
// Test for n=3
n = 3;
System.Console.WriteLine(is_divisible(n));
// Test for n=4
n = 4;
System.Console.WriteLine(is_divisible(n));
}
}
// This code is contributed by mits
PHP
<?php
// Function to check whether
// a number is prime or not.
function is_prime($num)
{
// Count variable to store
// the number of factors of 'num'
$count1 = 0;
// Counting the number of factors
for ($i = 1; $i * $i <= ($num); $i++)
{
if (($num) % $i == 0)
{
if ($i * $i != ($num))
$count1 += 2;
else
$count1++;
}
}
// If number is prime return true
if ($count1 == 2)
return true;
else
return false;
}
// Function to check for divisibility
function is_divisible($n)
{
// if 'n' equals 1 then divisibility is possible
if ($n == 1)
{
return "YES";
}
// Else check whether 'n+1' is prime or not
else
{
// If 'n+1' is prime then 'n!' is
// not divisible by 'n*(n+1)/2'
if (is_prime($n + 1))
return "NO";
// else divisibility occurs
else
return "YES";
}
}
// Driver Code
// Test for n=3
$n = 3;
echo is_divisible($n) . "\n";
// Test for n=4
$n = 4;
echo is_divisible($n) . "\n";
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// Function to check whether
// a number is prime or not.
function is_prime(num)
{
// Count variable to store
// the number of factors of 'num'
var count = 0;
// Counting the number of factors
for (i = 1; i * i <= (num); i++)
{
if ((num) % i == 0)
{
if (i * i != (num))
count += 2;
else
count++;
}
}
// If number is prime return true
if (count == 2)
return true;
else
return false;
}
// Function to check for divisibility
function is_divisible(n)
{
// if 'n' equals 1 then divisibility is possible
if (n == 1)
{
return "YES";
}
// Else check whether 'n+1' is prime or not
else
{
// If 'n+1' is prime then 'n!' is
// not divisible by 'n*(n+1)/2'
if (is_prime(n + 1))
return "NO";
// else divisibility occurs
else
return "YES";
}
}
// Driver Code
var n;
// Test for n=3
n = 3;
document.write(is_divisible(n)+"<br>");
// Test for n=4
n = 4;
document.write(is_divisible(n));
// This code is contributed by Princi Singh
</script>
Producción:
YES NO
Complejidad de tiempo: O (sqrtn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Mostafijur Rahaman y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA