ในปัญหานี้ เราได้จำนวนเต็มสองตัว n และ r งานของเราคือการหากำลังของจำนวนเฉพาะที่กำหนด r ในแฟกทอเรียลของจำนวน n
มาดูตัวอย่างทำความเข้าใจปัญหากัน
ป้อนข้อมูล − n =6 r =2
ผลผลิต − 4
คำอธิบาย −
Factorial n, 6! = 6*5*4*3*2*1 = 720 720 = 24 * 32 * 5, power of 2 is 4
ในการแก้ปัญหานี้ วิธีแก้ไขง่ายๆ คือ การหาแฟคทอเรียลโดยตรงแล้วจึงหากำลังของจำนวนเฉพาะ แต่นี่ไม่ใช่ทางออกที่ดีที่สุด
อีกวิธีที่มีประสิทธิภาพคือการใช้สูตร
พลังของ 'r' ใน n! =floor(n/r) + floor(n/r2) + floor(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
