ในปัญหานี้ เราได้รับตัวเลข n และจำนวนเฉพาะ p งานของเราคือ หากำลังของจำนวนเฉพาะ p ใน n!
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : n = 6, p = 2 Output : 4
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ ก็คือการหาค่าของ n! และแยกตัวประกอบแล้วหากำลังของจำนวนเฉพาะ p ในการแยกตัวประกอบ
ในที่นี้ ตัวเลขสามารถแสดงเป็นตัวประกอบกำลังของ 2 ใน 5! =30 คือ 3.
ค่าของ n แฟคทอเรียลคือ
$$n!\:=\:n^*(n-1)^*(n-2)^*(n-3)\dotso{^*}2^*1$$
$$n!\:=\:3^*2^*1\:=\:6$$
ให้เอา n =6 และ p =2
น! =6! =(2*3*4*5*6)
น! =720
การแยกตัวประกอบของ 720 คือ 2*2*2*2*3*3*5
พลังของ 2 ในการแยกตัวประกอบของ 6! คือ 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
