การแยกตัวประกอบเฉพาะด้วย Sieve O(log n) สำหรับหลาย Query ใน C++

บทนำ

Prime Factorization แบบปกติ O(√n) ช้าสำหรับหลาย Query ใช้ Sieve of Eratosthenes เตรียม Smallest Prime Factor (SPF) ไว้ก่อน แล้วแยกตัวประกอบได้ O(log n) ต่อ Query

ขั้นตอน

1. สร้างอาร์เรย์ SPF ขนาด N+1 โดย SPF[i] = ตัวหารเฉพาะน้อยที่สุดของ i
2. Sieve: เริ่ม SPF[i] = i, แล้วสำหรับทุก i ที่เป็นเฉพาะ (SPF[i]==i) ตั้ง SPF[j] = i สำหรับ j = i*i, i*i+i, ...
3. แยกตัวประกอบ n: วน while n != 1, พิมพ์ SPF[n], n /= SPF[n]

ตัวอย่างโค้ด

#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

ตรวจสอบ

2 × 13 × 37 × 47 = 2 × 13 = 26, 26 × 37 = 962, 962 × 47 = 45214 ✓

ประสิทธิภาพ

• Preprocessing Sieve: O(N log log N)
• แต่ละ Query: O(log n)
• เหมาะสำหรับหลาย Query (Multiple Queries)

สรุป

SPF Sieve เป็นเทคนิคมาตรฐานสำหรับ Prime Factorization หลายครั้ง ใช้ใน Competitive Programming บ่อยมาก