Given an integer N, the task is to count the number of prime factors of N!.
Examples:
Input: N = 5
Output: 3
Explanation: Factorial of 5 = 120. Prime factors of 120 are {2, 3, 5}. Therefore, the count is 3.Input: N = 1
Output: 0
Naive Approach: Follow the steps to solve the problem :
- Initialize a variable, say fac, to store the factorial of a number.
- Initialize a variable, say count, to count the prime factors of N!.
- Iterate over the range [2, fac], and if the number is not prime, increment count.
- Print the count as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// factorial of a numberint factorial(int f){ // Base Case if (f == 0 || f == 1) { return 1; } else { // Recursive call return (f * factorial(f - 1)); }}// Function to check if a// number is prime or notbool isPrime(int element){ for (int i = 2; i <= sqrt(element); i++) { if (element % i == 0) { // Not prime return false; } } // Is prime return true;}// Function to count the number// of prime factors of N!int countPrimeFactors(int N){ // Stores factorial of N int fac = factorial(N); // Stores the count of // prime factors int count = 0; // Iterate over the range [2, fac] for (int i = 2; i <= fac; i++) { // If not prime if (fac % i == 0 && isPrime(i)) { // Increment count count++; } } // Print the count cout << count;}// Driver Codeint main(){ // Given value of N int N = 5; // Function call to count the // number of prime factors of N countPrimeFactors(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to calculate // factorial of a number static int factorial(int f) { // Base Case if (f == 0 || f == 1) { return 1; } else { // Recursive call return (f * factorial(f - 1)); } } // Function to check if a // number is prime or not static boolean isPrime(int element) { for (int i = 2; i <= (int)Math.sqrt(element); i++) { if (element % i == 0) { // Not prime return false; } } // Is prime return true; } // Function to count the number // of prime factors of N! static void countPrimeFactors(int N) { // Stores factorial of N int fac = factorial(N); // Stores the count of // prime factors int count = 0; // Iterate over the range [2, fac] for (int i = 2; i <= fac; i++) { // If not prime if ((fac % i == 0 && isPrime(i))) { // Increment count count++; } } // Print the count System.out.println(count); } // Driver Code public static void main(String[] args) { // Given value of N int N = 5; // Function call to count the // number of prime factors of N countPrimeFactors(N); }}// This code is contributed by sanjoy_62. |
Python3
# Python program for the above approachfrom math import sqrt# Function to calculate# factorial of a numberdef factorial(f): # Base Case if (f == 0 or f == 1): return 1 else: # Recursive call return (f * factorial(f - 1)) # Function to check if a# number is prime or notdef isPrime(element): for i in range(2,int(sqrt(element))+1): if (element % i == 0): # Not prime return False # Is prime return True# Function to count the number# of prime factors of N!def countPrimeFactors(N): # Stores factorial of N fac = factorial(N) # Stores the count of # prime factors count = 0 # Iterate over the range [2, fac] for i in range(2, fac + 1): # If not prime if (fac % i == 0 and isPrime(i)): # Increment count count += 1 # Print the count print(count)# Driver Code# Given value of NN = 5# Function call to count the# number of prime factors of NcountPrimeFactors(N)# This code is contributed by shubhamsingh10 |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate // factorial of a number static int factorial(int f) { // Base Case if (f == 0 || f == 1) { return 1; } else { // Recursive call return (f * factorial(f - 1)); } } // Function to check if a // number is prime or not static bool isPrime(int element) { for (int i = 2; i <= (int)Math.Sqrt(element); i++) { if (element % i == 0) { // Not prime return false; } } // Is prime return true; } // Function to count the number // of prime factors of N! static void countPrimeFactors(int N) { // Stores factorial of N int fac = factorial(N); // Stores the count of // prime factors int count = 0; // Iterate over the range [2, fac] for (int i = 2; i <= fac; i++) { // If not prime if ((fac % i == 0 && isPrime(i))) { // Increment count count++; } } // Print the count Console.Write(count); }// Driver Codepublic static void Main(){ // Given value of N int N = 5; // Function call to count the // number of prime factors of N countPrimeFactors(N);}}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to calculate// factorial of a numberfunction factorial(f){ // Base Case if (f == 0 || f == 1){ return 1 } else{ // Recursive call return (f * factorial(f - 1)) } } // Function to check if a// number is prime or notfunction isPrime(element){ for (let i = 2; i < Math.floor(Math.sqrt(element)+1); i++){ if (element % i == 0){ // Not prime return false } } // Is prime return true}// Function to count the number// of prime factors of N!function countPrimeFactors(N){ // Stores factorial of N let fac = factorial(N) // Stores the count of // prime factors let count = 0 // Iterate over the range [2, fac] for(let i = 2; i < fac + 1; i++){ // If not prime if (fac % i == 0 && isPrime(i)){ // Increment count count += 1 } } // Print the count document.write(count)}// Driver Code// Given value of Nlet N = 5// Function call to count the// number of prime factors of NcountPrimeFactors(N)// This code is contributed by _saurabh_jaiswal</script> |
3
Time Complexity: O(N! * sqrt(N))
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Sieve Of Eratosthenes. Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the count of prime factors of N!.
- Initialize a boolean array, say prime[] to check if a number is prime or not.
- Perform Sieve of Eratosthenes and populate count at each iteration, if found prime.
- Print the value of count as the answer.
Below is the implementation of the above approach:
C++
// C++ approach for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the// prime factors of N!int countPrimeFactors(int N){ // Stores the count of // prime factors int count = 0; // Stores whether a number // is prime or not bool prime[N + 1]; // Mark all as true initially memset(prime, true, sizeof(prime)); // Sieve of Eratosthenes for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all subsequent multiples for (int i = p * p; i <= N; i += p) prime[i] = false; } } // Traverse in the range [2, N] for (int p = 2; p <= N; p++) { // If prime if (prime[p]) { // Increment the count count++; } } // Print the count cout << count;}// Driver Codeint main(){ // Given value of N int N = 5; // Function call to count // the prime factors of N! countPrimeFactors(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to count the // prime factors of N! static void countPrimeFactors(int N) { // Stores the count of // prime factors int count = 0; // Stores whether a number // is prime or not boolean[] prime = new boolean[N + 1]; // Mark all as true initially Arrays.fill(prime, true); // Sieve of Eratosthenes for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all subsequent multiples for (int i = p * p; i <= N; i += p) prime[i] = false; } } // Traverse in the range [2, N] for (int p = 2; p <= N; p++) { // If prime if (prime[p] != false) { // Increment the count count++; } } // Print the count System.out.print(count); } // Driver Code public static void main(String[] args) { // Given value of N int N = 5; // Function call to count // the prime factors of N! countPrimeFactors(N); }}// This code is contributed by susmitakundugoaldanga. |
Python3
# Python3 approach for the above approach# Function to count the# prime factors of N!def countPrimeFactors(N): # Stores the count of # prime factors count = 0 # Stores whether a number # is prime or not prime = [1] * (N + 1) # Sieve of Eratosthenes for p in range(2, N + 1): if p * p > N: break # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all subsequent multiples for i in range(p * p, N + 1, p): prime[i] = 0 # Traverse in the range [2, N] for p in range(2, N + 1): # If prime if (prime[p]): # Increment the count count += 1 # Print the count print (count)# Driver Codeif __name__ == '__main__': # Given value of N N = 5 # Function call to count # the prime factors of N! countPrimeFactors(N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;public class GFG { // Function to count the // prime factors of N! static void countPrimeFactors(int N) { // Stores the count of // prime factors int count = 0; // Stores whether a number // is prime or not bool[] prime = new bool[N + 1]; // Mark all as true initially for (int i = 0; i < prime.Length; i++) prime[i] = true; // Sieve of Eratosthenes for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all subsequent multiples for (int i = p * p; i <= N; i += p) prime[i] = false; } } // Traverse in the range [2, N] for (int p = 2; p <= N; p++) { // If prime if (prime[p] != false) { // Increment the count count++; } } // Print the count Console.Write(count); } // Driver Code public static void Main(String[] args) { // Given value of N int N = 5; // Function call to count // the prime factors of N! countPrimeFactors(N); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach // Function to count the // prime factors of N! function countPrimeFactors( N) { // Stores the count of // prime factors var count = 0; // Stores whether a number // is prime or not var prime = Array(N + 1).fill(true); // Sieve of Eratosthenes for (var p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all subsequent multiples for (var i = p * p; i <= N; i += p) prime[i] = false; } } // Traverse in the range [2, N] for (var p = 2; p <= N; p++) { // If prime if (prime[p] != false) { // Increment the count count++; } } // Print the count document.write(count); } // Driver Code // Given value of N var N = 5; // Function call to count // the prime factors of N! countPrimeFactors(N);// This code is contributed by Amit Katiyar</script> |
3
Time Complexity: O(N * log(logN))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/count-prime-factors-of-n/ […]
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/count-prime-factors-of-n/ […]
… [Trackback]
[…] Read More Information here to that Topic: geeksforgeeks.org/count-prime-factors-of-n/ […]