ในปัญหานี้ เราได้รับจำนวนเต็ม N <=10^18 งานของเราคือพิมพ์ตัวประกอบเฉพาะของจำนวนพร้อมกับความถี่ของการเกิด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: 100 Output: 2 2 5 2 Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.
ในการแก้ปัญหานี้ เราจะต้องหาตัวประกอบเฉพาะของตัวเลขแล้วคำนวณความถี่ของพวกมัน
สำหรับสิ่งนี้เราจะพบว่าตรวจสอบความถี่ของ 2 เป็นตัวประกอบแล้วหารจำนวนด้วย 2 จากนั้นตรวจสอบจาก 3 ถึงรากที่สอง n หารและเพิ่มความถี่ของจำนวนเฉพาะแต่ละตัวที่เป็นตัวประกอบของจำนวนนั้น และหยุดถ้าตัวเลขกลายเป็น 1 แล้วพิมพ์จำนวนเฉพาะทั้งหมดที่มีความถี่
โค้ดด้านล่างแสดงการใช้งานโซลูชันของเรา
ตัวอย่าง
#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
int count = 0;
while (!(n % 2)) {
n/= 2;
count++;
}
if (count)
cout<<2<<"\t"<<count<<endl;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count)
cout<<i<<"\t"<<count<<endl;
}
if (n > 2)
cout<<n<<"\t"<<1<<endl;
}
int main() {
long long N = 21000;
cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
factorize(N);
return 0;
} ผลลัพธ์
The prime factors and their frequencies of the number 21000 are 2 3 3 1 5 3 7 1
