Dado un entero positivo N , la tarea es comprobar si N es un factorial primo o no. Si es un primo factorial, imprima SÍ , de lo contrario imprima NO .
Nota: En matemáticas, un número primo factorial es un número primo que es uno menos o uno más que un factorial de cualquier número. Los primeros primos factoriales son 2, 3, 5, 7, 23, 719, 5039, … .
Ejemplos:
Entrada: N = 23
Salida: SI
23 es un número primo y uno menor que el factorial de 4 (4! = 24).
Entrada: 11
Salida: NO
11 es un número primo pero no se puede expresar como n. + 1 o n! – 1.
Enfoque: para que N sea un número factorial, N debe ser un número primo y N – 1 o N + 1 debe ser el valor del factorial de cualquier número.
- Si N no es primo , imprima No.
- De lo contrario, establezca fact = 1 y, a partir de i = 1 , actualice fact = fact * i , si fact = N – 1 o fact = N + 1 luego imprima Sí .
- Repita el paso anterior hasta que fact ≤ N + 1 y si la condición no se cumple, imprima No al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if given
// number is a factorial prime
#include <bits/stdc++.h>
using namespace std;
// Utility function to check
// if a number is prime or not
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 returns true if n is a factorial prime
bool isFactorialPrime(long n)
{
// If n is not prime then return false
if (!isPrime(n))
return false;
long fact = 1;
int i = 1;
while (fact <= n + 1) {
// Calculate factorial
fact = fact * i;
// If n is a factorial prime
if (n + 1 == fact || n - 1 == fact)
return true;
i++;
}
// n is not a factorial prime
return false;
}
// Driver code
int main()
{
int n = 23;
if (isFactorialPrime(n))
cout << "Yes";
else
cout << "No";
return 0;
}
C
// C program to check if given
// number is a factorial prime
#include <stdio.h>
#include<stdbool.h>
// Utility function to check
// if a number is prime or not
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 returns true if n is a factorial prime
bool isFactorialPrime(long n)
{
// If n is not prime then return false
if (!isPrime(n))
return false;
long fact = 1;
int i = 1;
while (fact <= n + 1) {
// Calculate factorial
fact = fact * i;
// if n is a factorial prime
if (n + 1 == fact || n - 1 == fact)
return true;
i++;
}
// n is not a factorial prime
return false;
}
// Driver code
int main()
{
int n = 23;
if (isFactorialPrime(n))
printf("Yes");
else
printf("No");
return 0;
}
// This code is contributed by allwink45.
Java
// Java program to check if given
// number is a factorial prime
class GFG {
// Utility function to check
// if a number is prime or not
static boolean isPrime(long 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 returns true if n is a factorial prime
static boolean isFactorialPrime(long n)
{
// If n is not prime then return false
if (!isPrime(n))
return false;
long fact = 1;
int i = 1;
while (fact <= n + 1) {
// Calculate factorial
fact = fact * i;
// If n is a factorial prime
if (n + 1 == fact || n - 1 == fact)
return true;
i++;
}
// n is not a factorial prime
return false;
}
// Driver code
public static void main(String args[])
{
int n = 23;
if (isFactorialPrime(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program to check if given
# number is a factorial prime
# from math lib import sqrt function
from math import sqrt
# Utility function to check
# if a number is prime or not
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 returns true if n
# is a factorial prime
def isFactorialPrime(n) :
# If n is not prime then return false
if (not isPrime(n)) :
return False
fact = 1
i = 1
while (fact <= n + 1) :
# Calculate factorial
fact = fact * i
# If n is a factorial prime
if (n + 1 == fact or n - 1 == fact) :
return True
i += 1
# n is not a factorial prime
return False
# Driver code
if __name__ == "__main__" :
n = 23
if (isFactorialPrime(n)) :
print("Yes")
else :
print("No")
# This code is contributed by Ryuga
C#
// C# program to check if given
// number is a factorial prime
using System;
class GFG {
// Utility function to check
// if a number is prime or not
static bool isPrime(long 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 returns true if n is a factorial prime
static bool isFactorialPrime(long n)
{
// If n is not prime then return false
if (!isPrime(n))
return false;
long fact = 1;
int i = 1;
while (fact <= n + 1) {
// Calculate factorial
fact = fact * i;
// If n is a factorial prime
if (n + 1 == fact || n - 1 == fact)
return true;
i++;
}
// n is not a factorial prime
return false;
}
// Driver code
public static void Main()
{
int n = 23;
if (isFactorialPrime(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
PHP
<?php
// PHP program to check if given number
// is a factorial prime
// Utility function to check if a
// number is prime or not
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 returns true if
// n is a factorial prime
function isFactorialPrime($n)
{
// If n is not prime then return false
if (!isPrime($n))
return false;
$fact = 1;
$i = 1;
while ($fact <= $n + 1)
{
// Calculate factorial
$fact = $fact * $i;
// If n is a factorial prime
if ($n + 1 == $fact || $n - 1 == $fact)
return true;
$i++;
}
// n is not a factorial prime
return false;
}
// Driver code
$n = 23;
if (isFactorialPrime($n))
echo "Yes";
else
echo "No";
// This code is contributed by ita_c
?>
Javascript
// Javascript program to check if given number
// is a factorial prime
// Utility function to check if a
// number is prime or not
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 (let i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function that returns true if
// n is a factorial prime
function isFactorialPrime(n)
{
// If n is not prime then return false
if (!isPrime(n))
return false;
let fact = 1;
let i = 1;
while (fact <= n + 1)
{
// Calculate factorial
fact = fact * i;
// If n is a factorial prime
if (n + 1 == fact || n - 1 == fact)
return true;
i++;
}
// n is not a factorial prime
return false;
}
// Driver code
let n = 23;
if (isFactorialPrime(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by gfgking
Producción:
Yes
Complejidad de tiempo: O (sqrtn)
Espacio Auxiliar: O(1)