Given a positive integer N, the task is to check if N is a Factorial prime or not. If it is a factorial prime then print YES else print NO.
Note: In mathematics, a factorial prime number is a prime number that is one less than or one more than a factorial of any number. First few factorial primes are 2, 3, 5, 7, 23, 719, 5039, ….
Examples:Â
Â
Input: N = 23Â
Output: YESÂ
23 is a prime number and one less than factorial of 4 (4! = 24).Â
Input: 11Â
Output: NOÂ
11 is a prime number but can not be expressed as either n! + 1 or n! – 1.Â
Â
Â
Approach: In order for N to be factorial number, N must be a prime and either N – 1 or N + 1 should be the value of factorial of any number.Â
Â
- If N is not prime then print No.
- Else set fact = 1 and starting from i = 1 update fact = fact * i, if fact = N – 1 or fact = N + 1 then print Yes.
- Repeat the above step until fact ? N + 1 and if the condition is not satisfied then print No in the end.
Below is the implementation of the above approach:
Â
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 notbool 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 primebool 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 codeint 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 notbool 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 primebool 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 codeint 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 primeclass 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 functionfrom 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 primeusing 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 notfunction 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 primefunction 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 notfunction 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 primefunction 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 codelet n = 23;Â
if (isFactorialPrime(n))    document.write("Yes");else    document.write("No");Â
// This code is contributed by gfgking |
Output:Â
Yes
Â
Time Complexity: O(sqrtn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
