# Finding power of prime number p in n!

Given a number ‘n’ and a prime number ‘p’. We need to find out the power of ‘p’ in prime factorization of n!

Examples:

```Input  : n = 4, p = 2
Output : 3
Power of 2 in prime factorization
of 2 in 4! = 24 is 3

Input  : n = 24, p = 2
Output : 22
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive approach
The naive approach is to find the power of p in each number from 1 to n and add them.Because we know that during multiplication power are added.

## C/C++

 `// C++ implementation of finding  ` `// power of p in n! ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Returns power of p in n! ` `int` `PowerOFPINnfactorial(``int` `n, ``int` `p) ` `{ ` `    ``// initializing answer ` `    ``int` `ans = 0; ` ` `  `    ``// initializing ` `    ``int` `temp = p; ` ` `  `    ``// loop until temp<=n ` `    ``while` `(temp <= n) { ` ` `  `        ``// add number of numbers divisible by n ` `        ``ans += n / temp; ` ` `  `        ``// each time multiply temp by p ` `        ``temp = temp * p; ` `    ``} ` `    ``return` `ans; ` `} ` ` `  `// Driver function ` `int` `main() ` `{ ` `    ``cout << PowerOFPINnfactorial(4, 2) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java implementation of naive approach ` ` `  `public` `class` `GFG  ` `{ ` `    ``// Method to calculate power of prime number p in n! ` `    ``static` `int` `PowerOFPINnfactorial(``int` `n, ``int` `p) ` `    ``{ ` `        ``// initializing answer ` `        ``int` `ans = ``0``; ` `      `  `        ``// finding power of p from 1 to n ` `        ``for` `(``int` `i = ``1``; i <= n; i++) { ` `      `  `            ``// variable to note the power of p in i ` `            ``int` `count = ``0``, temp = i; ` `      `  `            ``// loop until temp is equal to i ` `            ``while` `(temp % p == ``0``) { ` `                ``count++; ` `                ``temp = temp / p; ` `            ``} ` `      `  `            ``// adding count to i ` `            ``ans += count; ` `        ``} ` `        ``return` `ans; ` `    ``} ` `     `  `    ``// Driver Method ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``System.out.println(PowerOFPINnfactorial(``4``, ``2``)); ` `    ``} ` `} `

## Python3

 `# Pyhton3 implementation of  ` `# finding power of p in n! ` ` `  `# Returns power of p in n! ` `def` `PowerOFPINnfactorial(n, p): ` ` `  `    ``# initializing answer ` `    ``ans ``=` `0``; ` ` `  `    ``# initializing ` `    ``temp ``=` `p; ` ` `  `    ``# loop until temp<=n ` `    ``while` `(temp <``=` `n): ` ` `  `        ``# add number of numbers  ` `        ``# divisible by n ` `        ``ans ``+``=` `n ``/` `temp; ` ` `  `        ``# each time multiply ` `        ``# temp by p ` `        ``temp ``=` `temp ``*` `p; ` `         `  `    ``return` `ans; ` ` `  `# Driver Code ` `print``(PowerOFPINnfactorial(``4``, ``2``)); ` ` `  `# This code is contributed by  ` `# mits `

/div>

## C#

 `// C# implementation of naive approach ` `using` `System; ` ` `  `public` `class` `GFG  ` `{ ` `    ``// Method to calculate power ` `    ``// of prime number p in n! ` `    ``static` `int` `PowerOFPINnfactorial(``int` `n, ``int` `p) ` `    ``{ ` `        ``// initializing answer ` `        ``int` `ans = 0; ` `     `  `        ``// finding power of p from 1 to n ` `        ``for` `(``int` `i = 1; i <= n; i++) { ` `     `  `            ``// variable to note the power of p in i ` `            ``int` `count = 0, temp = i; ` `     `  `            ``// loop until temp is equal to i ` `            ``while` `(temp % p == 0) { ` `                ``count++; ` `                ``temp = temp / p; ` `            ``} ` `     `  `            ``// adding count to i ` `            ``ans += count; ` `        ``} ` `        ``return` `ans; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main(String []args) ` `    ``{ ` `        ``Console.WriteLine(PowerOFPINnfactorial(4, 2)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output:

```3
```

Efficient Approach
Before discussing efficient approach lets discuss a question given a two numbers n, m how many numbers are there from 1 to n that are divisible by m the answer is floor(n/m).
Now coming back to our original question to find power of p in n! what we do is count the number of numbers from 1 to n that are divisible by p then by then by till > n and add them . This will be our required answer.

`   Powerofp(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3)........ `

Below is implementation of above steps.

## C/C++

 `// C++ implementation of finding power of p in n! ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Returns power of p in n! ` `int` `PowerOFPINnfactorial(``int` `n, ``int` `p) ` `{ ` `    ``// initializing answer ` `    ``int` `ans = 0; ` ` `  `    ``// initializing ` `    ``int` `temp = p; ` ` `  `    ``// loop until temp<=n ` `    ``while` `(temp <= n) { ` ` `  `        ``// add number of numbers divisible by n ` `        ``ans += n / temp; ` ` `  `        ``// each time multiply temp by p ` `        ``temp = temp * p; ` `    ``} ` `    ``return` `ans; ` `} ` ` `  `// Driver function ` `int` `main() ` `{ ` `    ``cout << PowerOFPINnfactorial(4, 2) << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java implementation of finding power of p in n! ` ` `  `public` `class` `GFG  ` `{ ` `    ``// Method to calculate power of prime number p in n! ` `    ``static` `int` `PowerOFPINnfactorial(``int` `n, ``int` `p) ` `    ``{ ` `        ``// initializing answer ` `        ``int` `ans = ``0``; ` `      `  `        ``// initializing ` `        ``int` `temp = p; ` `      `  `        ``// loop until temp<=n ` `        ``while` `(temp <= n) { ` `      `  `            ``// add number of numbers divisible by n ` `            ``ans += n / temp; ` `      `  `            ``// each time multiply temp by p ` `            ``temp = temp * p; ` `        ``} ` `        ``return` `ans; ` `    ``} ` `     `  `    ``// Driver Method ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``System.out.println(PowerOFPINnfactorial(``4``, ``2``)); ` `    ``} ` `} `

## Python3

 `# Python3 implementation of ` `# finding power of p in n! ` ` `  `# Returns power of p in n! ` `def` `PowerOFPINnfactorial(n, p): ` ` `  `    ``# initializing answer ` `    ``ans ``=` `0` ` `  `    ``# initializing ` `    ``temp ``=` `p ` ` `  `    ``# loop until temp<=n ` `    ``while` `(temp <``=` `n) : ` ` `  `        ``# add number of numbers  ` `        ``# divisible by n ` `        ``ans ``+``=` `n ``/` `temp ` ` `  `        ``# each time multiply  ` `        ``# temp by p ` `        ``temp ``=` `temp ``*` `p ` `     `  `    ``return` `int``(ans) ` ` `  `# Driver Code ` `print``(PowerOFPINnfactorial(``4``, ``2``)) ` ` `  `# This code is contributed  ` `# by Smitha `

## C#

 `// C# implementation of finding  ` `// power of p in n! ` `using` `System; ` ` `  `public` `class` `GFG  ` `{ ` ` `  `    ``// Method to calculate power ` `    ``// of prime number p in n! ` `    ``static` `int` `PowerOFPINnfactorial(``int` `n, ``int` `p) ` `    ``{ ` `        ``// initializing answer ` `        ``int` `ans = 0; ` `     `  `        ``// initializing ` `        ``int` `temp = p; ` `     `  `        ``// loop until temp <= n ` `        ``while` `(temp <= n) { ` `     `  `            ``// add number of numbers divisible by n ` `            ``ans += n / temp; ` `     `  `            ``// each time multiply temp by p ` `            ``temp = temp * p; ` `        ``} ` `        ``return` `ans; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main(String []args) ` `    ``{ ` `        ``Console.WriteLine(PowerOFPINnfactorial(4, 2)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output:

```3
```

Time Complexity :O( (n))