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