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 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 |
Yes
Time Complexity: O(sqrtn)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!