n의 소수 r의 거듭제곱! C++에서

이 문제에서는 두 개의 정수 n과 r이 주어집니다. 우리의 임무는 숫자 n의 계승에서 주어진 소수 r의 거듭제곱을 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 − n =6 r =2

출력 - 4

설명 -

Factorial n, 6! = 6*5*4*3*2*1 = 720
720 = 24 * 32 * 5, power of 2 is 4

이 문제를 해결하기 위해 간단한 솔루션은 계승을 직접 찾은 다음 소수의 거듭제곱을 찾는 것입니다. 그러나 이것이 최선의 해결책은 아닙니다.

또 다른 효율적인 솔루션은 공식을 사용하는 것입니다.

n의 'r'의 힘! =바닥(n/r) + 바닥(n/r2) + 바닥(n/r3) + ...

예

솔루션 구현을 보여주는 프로그램,

#include <iostream>
using namespace std;
int primePower(int n, int r) {
   int count = 0;
   for (int i = r; (n / i) >= 1; i = i * r)
      count = count+n/i;
   return count;
}
int main() {
   int n = 6, r = 2;
   cout<<"Power of prime number "<<r<<"in factorial "<<n<<" is : "<<primePower(n, r);
   return 0;
}

출력

Power of prime number 2in factorial 6 is : 4