ในปัญหานี้ เราจำเป็นต้องสร้างโปรแกรมเพื่อคำนวณ Prime Factorization โดยใช้ Sieve O(log n) สำหรับการสืบค้นหลายรายการ
เนื่องจากวิธีการทั่วไปนั้นใช้เวลา O(sqrt(n) ) ซึ่งจะเพิ่มเวลาที่ต้องใช้อย่างมากจากการสืบค้นหลายรายการ
มาสรุปกันก่อน
แยกตัวประกอบเฉพาะ ของตัวเลขจะรวมเฉพาะตัวประกอบเฉพาะ ไม่ใช่ผลคูณของตัวประกอบเฉพาะเหล่านั้น
ตะแกรงของ Eratosthenes เป็นอัลกอริทึมในการสร้างจำนวนเฉพาะทั้งหมดภายในช่วงที่กำหนด
แนวทางการแก้ปัญหา
วิธีแก้ไขปัญหาพบได้โดยการหาตัวประกอบที่เล็กที่สุดที่หารจำนวนนั้น บันทึกเป็นปัจจัยและอัปเดตตัวเลขโดยหารด้วยตัวประกอบ กระบวนการนี้ดำเนินการซ้ำๆ จนกระทั่งจำนวนกลายเป็น 1 หลังจากการหาร ซึ่งหมายความว่าไม่มีปัจจัยอื่นใดที่เป็นไปได้
การคำนวณทำได้โดยใช้ ตะแกรงอีราทอสเทนีส ซึ่งลดความซับซ้อนของเวลาในการหาตัวประกอบเฉพาะที่เล็กที่สุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int primes[100001];
void sieveOfEratosthenes(int N) {
N+=2;
primes[1] = 1;
for (int i=2; i<N; i++)
primes[i] = i;
for (int i=4; i<N; i+=2)
primes[i] = 2;
for (int i=3; i*i<N; i++) {
if (primes[i] == i) {
for (int j=i*i; j<N; j+=i)
if (primes[j]==j)
primes[j] = i;
}
}
}
void findPrimeFactors(int num) {
sieveOfEratosthenes(num);
int factor;
while (num != 1) {
factor = primes[num];
cout<<factor<<" ";
num /= factor;
}
}
int main() {
int N = 45214;
cout<<"Prime factorization of the number "<<N<<" using sieve is ";
findPrimeFactors(N);
return 0;
} ผลลัพธ์
Prime factorization of the number 45214 using sieve is 2 13 37 47
