Given a positive integer N and a prime p, the task is to print the largest power of prime p that divides N!. Here N! means the factorial of N = 1 x 2 x 3 . . (N-1) x N.
Note that the largest power may be 0 too.
 
Example 1:
Input:
N = 5 , p = 2
Output:
3
Explanation:
5! = 120. The highest x for which 2^{x}
divides 120 is 3, as 120%8 = 0.
So, the Output is 3.
Example 2:
Input:
N = 3 , p = 5
Output:
0
Explanation:
3! = 6. The highest x for which 5^{x}
divides 6 is 0, as 6%1 = 0.
So, the Output is 0.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function largestPowerOfPrime() which takes 2 Integers N and p as input and returns the answer.
 
Expected Time Complexity: O(log_{p}(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
2 <= p <= 5000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def largestPowerOfPrime(self, N, p):

        # code here 

Solutions:
class Solution:

	def largestPowerOfPrime(self, N, p):
		sum = 0
		while N:
			N //= p
			sum += N
		return sum


import math

class Solution:

	def largestPowerOfPrime(self, N, p):
		sum = 0
		while N:
			N /= p
			sum += int(N)
		return int(sum)


class Solution:

	def largestPowerOfPrime(self, N, p):
		sum = 0
		while N > 0:
			sum += N // p
			N = N // p
		return sum
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, p) = map(int, input().split())
		ob = Solution()
		print(ob.largestPowerOfPrime(N, p))


import math

class Solution:

	def factorial(self, x):
		ret = 1
		for i in range(1, x + 1):
			ret *= i
		return ret

	def sub(self, n, p, x, visited=[]):
		if n % p ** x == 0:
			visited.append(x)
		elif p ** x >= math.sqrt(n):
			return visited[-1] if len(visited) > 0 else 0
		return self.sub(n, p, x + 1, visited)

	def largestPowerOfPrime(self, N, p):
		res = 0
		while N:
			N //= p
			res += N
		return res


import math

class Solution:

	def largestPowerOfPrime(self, N, p):
		res = 0
		while N:
			N = N // p
			res += N
		return res