Find all factorial numbers less than or equal to n
A number N is called a factorial number if it is the factorial of a positive integer. For example, the first few factorial numbers are
1, 2, 6, 24, 120, …
Given a number n, print all factorial numbers smaller than or equal to n.
Examples :
Input: n = 100
Output: 1 2 6 24Input: n = 1500
Output: 1 2 6 24 120 720
A simple solution is to generate all factorials one by one until the generated factorial is greater than n.
An efficient solution is to find next factorial using previous factorial.
C++
// CPP program to find all factorial numbers // smaller than or equal to n. #include <iostream> using namespace std; void printFactorialNums( int n) { int fact = 1; int x = 2; while (fact <= n) { cout << fact << " " ; // Compute next factorial // using previous fact = fact * x; x++; } } // Driver code int main() { int n = 100; printFactorialNums(n); return 0; } |
Java
// Java program to find all factorial numbers // smaller than or equal to n. class GFG { static void printFactorialNums( int n) { int fact = 1 ; int x = 2 ; while (fact <= n) { System.out.print(fact + " " ); // Compute next factorial // using previous fact = fact * x; x++; } } // Driver code public static void main (String[] args) { int n = 100 ; printFactorialNums(n); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find all factorial # numbers smaller than or equal to n. def printFactorialNums( n): fact = 1 x = 2 while fact < = n: print (fact, end = " " ) # Compute next factorial # using previous fact = fact * x x + = 1 # Driver code n = 100 printFactorialNums(n) # This code is contributed by "Abhishek Sharma 44" |
C#
// C# program to find all factorial numbers // smaller than or equal to n. using System; class GFG { static void printFactorialNums( int n) { int fact = 1; int x = 2; while (fact <= n) { Console.Write(fact + " " ); // Compute next factorial // using previous fact = fact * x; x++; } } // Driver code public static void Main () { int n = 100; printFactorialNums(n); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find all // factorial numbers smaller // than or equal to n. function printFactorialNums( $n ) { $fact = 1; $x = 2; while ( $fact <= $n ) { echo $fact , " " ; // Compute next factorial // using previous $fact = $fact * $x ; $x ++; } } // Driver code $n = 100; echo printFactorialNums( $n ); // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript program to find all factorial numbers // smaller than or equal to n. function printFactorialNums(n) { let fact = 1; let x = 2; while (fact <= n) { document.write(fact + " " ); // Compute next factorial // using previous fact = fact * x; x++; } } // Driver code let n = 100; printFactorialNums(n); // This code is contributed by Mayank Tyagi </script> |
1 2 6 24
Time Complexity: O(x)
Auxiliary Space: O(1)
Another solution : we can print factorial of a number such that factorial <=n by recursion.
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to Print factorial using Recursion void PrintFactorialNums( int n, int fac, int i) { i++; if (fac > n) // if fac>n return because { return ; } // we have to find in [1,N] cout << fac << " " ; // print Factors // recursive call PrintFactorialNums(n, fac * i, i); } // Drive Code int main() { int n = 100; // Function call PrintFactorialNums(n, 1, 1); return 0; } // This code is contributed by nikhilsainiofficial546 |
Java
import java.util.*; class Main { // Function to Print factorial using Recursion static void PrintFactorialNums( int n, int fac, int i) { i++; if (fac > n) { // if fac>n return because return ; } // we have to find in [1,N] System.out.print(fac + " " ); // print Factors // recursive call PrintFactorialNums(n, fac * i, i); } // Drive Code public static void main(String[] args) { int n = 100 ; // Function call PrintFactorialNums(n, 1 , 1 ); } } |
Python3
def print_factorial_nums(n, fac, i): # Recursive function to print factors of n! i + = 1 if fac > n: # If fac becomes greater than n, return from the function # because we only need to find the factors up to n return print (fac, end = ' ' ) # print the current factor # Recursive call to print the next factor print_factorial_nums(n, fac * i, i) # Driver code if __name__ = = '__main__' : n = 100 print_factorial_nums(n, 1 , 1 ) |
C#
using System; using System.Collections; using System.Collections.Generic; using System.Linq; // C# code implementation of the above approach. class HelloWorld { // Function to Print factorial using Recursion public static void PrintFactorialNums( int n, int fac, int i) { i++; if (fac > n) { // if fac>n return because return ; } // we have to find in [1,N] Console.Write(fac + " " ); // print Factors // recursive call PrintFactorialNums(n, fac * i, i); } static void Main() { int n = 100; // Function call PrintFactorialNums(n, 1, 1); } } // The code is contributed by Nidhi goel. |
Javascript
temp= "" ; function print_factorial_nums(n, fac, i) { // Recursive function to print factors of n! i += 1; if (fac > n) { // If fac becomes greater than n, return from the function // because we only need to find the factors up to n return ; } temp = temp + fac + " " ; // print the current factor // Recursive call to print the next factor print_factorial_nums(n, fac * i, i); } // Driver code let n = 100; print_factorial_nums(n, 1, 1); console.log(temp); |
1 2 6 24
Time Complexity: O(n)
Auxiliary Space: O(n)
If there are multiple queries, then we can cache all previously computed factorial numbers to avoid re-computations.
Contact Us