N!에서 소수 p 등장 횟수 구하기

$ N! $ 을 소인수분해 했을 때 소수 $ p $ 가 몇 번 나오는지 찾는 알고리즘입니다.

1. $ N $ 을 $ p $ 로 나눈 몫을 구합니다. 1에서 $ N $ 까지의 숫자 중 $ p $ 를 소인수로 가지는 수의 개수를 구할 수 있습니다.
2. $ N $ 을 $ p^2 $로 나눈 몫을 구합니다. 1에서 $ N $ 까지의 숫자 중 $p^2$ 를 소인수로 가지는 수의 개수를 구할 수 있습니다.
3. 이런 식으로 몫이 0이 될 때 까지 계속 합니다.
4. 나온 숫자를 모두 더해줍니다.

#include<iostream>
using namespace std;
int main() {
	int n, p, cur_p, count = 0;
	cin >> n >> p;
	cur_p = p;
	while (n / cur_p != 0) {
		count += n / cur_p;
		cur_p *= p;
	}
	cout << "소인수 개수 : " << count;
	return 0;
}

 

이렇게 하면 $ O(log\ n) $ 에 구할 수 있습니다.

---

이 알고리즘의 명칭은 모르겠습니다. GPT도 모르더라고요