이 문제에서는 숫자 n과 소수 p가 주어집니다. 우리의 임무는 n에서 소수 p의 거듭제곱을 구하는 것입니다!
문제를 이해하기 위해 예를 들어 보겠습니다.
Input : n = 6, p = 2 Output : 4
해결 방법
문제에 대한 간단한 해결책은 단순히 n!의 값을 찾는 것입니다. 그리고 그것을 인수분해하고, 인수분해에서 소수 p의 거듭제곱을 구하세요.
여기서 숫자는 2 in 5의 역률로 나타낼 수 있습니다! =30은 3입니다.
n 계승의 값은
$$n!\:=\:n^*(n-1)^*(n-2)^*(n-3)\dotso{^*}2^*1$$
$$n!\:=\:3^*2^*1\:=\:6$$
n =6 및 p =2,
N! =6! =(2*3*4*5*6)
N! =720
720의 인수분해는 2*2*2*2*3*3*5입니다.
6의 인수분해에서 2의 거듭제곱! 4입니다.
따라서 출력은 4입니다.
예
솔루션 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
int powerOfPrimeNfactorial(int N, int P){
int primePower = 0;
int factVal = P;
while (factVal <= N) {
primePower += N / factVal;
factVal = factVal * P;
}
return primePower;
}
int main(){
int N = 6;
int P = 2;
cout<<"The power of prime number "<<P<<" in "<<N<<"! is "<<powerOfPrimeNfactorial(N, P) << endl;
return 0;
} 출력
The power of prime number 2 in 6! is 4