ในปัญหานี้ ให้จำนวนเต็ม n และ r (ซึ่งเป็นจำนวนเฉพาะ) ต้องหาว่า r ปรากฏเป็นตัวประกอบกี่ครั้งใน n! (แฟกทอเรียลของ n)
ตัวอย่าง
Input − n = 6, r = 2
Output − 4
คำอธิบาย −
6! = 6×5×4×3×2×1 = 720 720 = 2⁴ × 3² × 5 กำลังของ 2 คือ 4
วิธีแก้ที่มีประสิทธิภาพ: สูตร Legendre's Formula
แทนที่จะคำนวณแฟกทอเรียล (ซึ่งใหญ่มากเร็วๆ) ใช้สูตร:
กำลังของ r ใน n! = ⌊n/r⌋ + ⌊n/r²⌋ + ⌊n/r³⌋ + ... (จนกว่าจะเป็น 0)
ตัวอย่างโค้ด C++
#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 += 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 2 in factorial 6 is : 4
การทำงานของโค้ด
- i = 2: count += 6/2 = 3
- i = 4: count += 6/4 = 1
- i = 8: 6/8 = 0 หยุดลูป
- ผลรวม = 4
