แนวคิด
ด้วยความเคารพของสองตัวเลขที่ให้มา P และ Q ( P และ Q สามารถมีค่าได้ถึง 10^6 ) ซึ่งสร้างตัวเลขN =(P!/Q!) หน้าที่ของเราคือลด N เป็น 1 โดยดำเนินการตามจำนวนการดำเนินการสูงสุดที่เป็นไปได้ โปรดจำไว้ว่า ในแต่ละการดำเนินการ เราสามารถแทนที่ N ด้วย N/X ถ้า N หารด้วย X ลงตัว กำหนดจำนวนสูงสุดของการดำเนินการที่เป็นไปได้
อินพุต
A = 7, B = 4
ผลลัพธ์
4
คำอธิบาย
N คือ 210 และตัวหารคือ 2, 3, 5, 7
อินพุต
A = 3, B = 1
ผลลัพธ์
2
คำอธิบาย
N คือ 6 และตัวหารคือ 2,3
วิธีการ
สังเกตได้ว่าการแยกตัวประกอบของจำนวน P!/Q! เหมือนกับการแยกตัวประกอบของตัวเลข(Q + 1)*(Q + 2)*…*(P – 1)*P.
นอกจากนี้ ควรสังเกตด้วยว่า จำนวนการดำเนินการจะสูงสุดหากเราหาร N ด้วยปัจจัยเฉพาะเท่านั้น ด้วยเหตุนี้ เราจึงต้องกำหนดจำนวนปัจจัยเฉพาะของ N ซึ่งรวมถึงจำนวนที่ซ้ำกันด้วย
สมมติให้นับจำนวนตัวประกอบเฉพาะในการแยกตัวประกอบของทุกจำนวนตั้งแต่ 2 ถึง 1000000
ขั้นแรก ใช้ ตะแกรงของ Eratosthenes เพื่อหาตัวหารเฉพาะของตัวเลขแต่ละตัว มีคำอธิบายดังนี้ −
-
สร้างรายการจำนวนเต็มตั้งแต่ 2 ถึง N:(2, 3, 4, …, N)
-
ในตอนแรก ถือว่า p เท่ากับ 2 ซึ่งเป็นจำนวนเฉพาะตัวแรก
-
เริ่มจาก p^2 ให้นับขึ้นทีละ p และระบุตัวเลขแต่ละตัวที่มากกว่าหรือเท่ากับ p^2 ในรายการ ดังนั้น ตัวเลขเหล่านี้อาจเป็น p(p+1), p(p+2), p(p+3) เป็นต้น..
-
กำหนดจำนวนแรกที่มากกว่า p ในรายการที่ไม่ได้ระบุไว้ เห็นว่าหากไม่มีตัวเลขดังกล่าวให้หยุด มิฉะนั้น ให้ถือว่า p เท่ากับตัวเลขนี้ (ซึ่งระบุจำนวนเฉพาะตัวถัดไป) และทำซ้ำอีกครั้งจากขั้นตอนที่ 3
หลังจากใช้วิธี Sieve of Eratosthenes เราสามารถคำนวณจำนวนปัจจัยเฉพาะในการแยกตัวประกอบของการใช้สูตรต่อไปนี้ -
ไพรม์แฟคเตอร์[num] =ไพรม์แฟกเตอร์[num / primedivisor[num]] + 1 ณ ปัจจุบัน เราสามารถใช้ prefix sum array สำหรับปัจจัยเฉพาะแล้วตอบสำหรับช่วงผลรวม [P, Q]
ตัวอย่าง
// CPP program to find maximum
// number moves possible
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Used to store number of prime
// factors of each number
int primeFactors1[N];
// Shows Function to find number of prime
// factors of each number
void findPrimeFactors(){
for (int a = 2; a < N; a++)
// Now if a is a prime number
if (primeFactors1[a] == 0)
for (int b = a; b < N; b += a)
// Now increase value by one from
// it's preveious multiple
primeFactors1[b] = primeFactors1[b / a] + 1;
// Build prefix sum
// this will be helpful for
// multiple test cases
for (int a = 1; a < N; a++)
primeFactors1[a] += primeFactors1[a - 1];
}
// Driver Code
int main(){
// Create primeFactors1 array
findPrimeFactors();
int P = 7, Q = 4;
// required answer
cout << primeFactors1[P] - primeFactors1[Q];
return 0;
} ผลลัพธ์
4
