Prime Numbers

จำนวนเฉพาะ (Prime Number) คือจำนวนเต็มบวกที่มากกว่า 1 และหารลงตัวด้วย 1 กับตัวเองเท่านั้น

ตรวจสอบจำนวนเฉพาะ

วิธีพื้นฐาน $O(\sqrt{n})$

bool isPrime(long long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

ทำไมแค่ $\sqrt{n}$?

ถ้า $n = a \times b$ และ $a \leq b$ แล้ว $a \leq \sqrt{n}$

ดังนั้นถ้าไม่มีตัวหารที่ $\leq \sqrt{n}$ แสดงว่า $n$ เป็นจำนวนเฉพาะ

Sieve of Eratosthenes

หาจำนวนเฉพาะทั้งหมดตั้งแต่ 2 ถึง n ใน $O(n \log \log n)$

วิธีการ

1. สร้าง array isPrime[0..n] เริ่มต้นเป็น true ทั้งหมด
2. เริ่มจาก 2 ไล่ mark ตัวคูณของมันเป็น false
3. ข้ามไปที่ตัวเลขถัดไปที่ยังเป็น true และทำซ้ำ

const int MAXN = 1e7 + 5;
bool isPrime[MAXN];
vector<int> primes;

void sieve(int n) {
    fill(isPrime, isPrime + n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // เก็บ prime ไว้ใน vector
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
}

Visualization

เริ่มต้น: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

หลัง mark คูณของ 2:
        2 3 X 5 X 7 X 9 X  11 X  13 X  15 ...

หลัง mark คูณของ 3:
        2 3 X 5 X 7 X X X  11 X  13 X  X  ...

เหลือ primes: 2, 3, 5, 7, 11, 13, ...

Linear Sieve $O(n)$

Sieve ที่เร็วกว่า โดยแต่ละ composite number ถูก mark เพียงครั้งเดียว

const int MAXN = 1e7 + 5;
int spf[MAXN]; // smallest prime factor
vector<int> primes;

void linearSieve(int n) {
    fill(spf, spf + n + 1, 0);
    
    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) { // i เป็น prime
            spf[i] = i;
            primes.push_back(i);
        }
        
        for (int p : primes) {
            if (p > spf[i] || (long long)i * p > n) break;
            spf[i * p] = p;
        }
    }
}

ประโยชน์เพิ่มเติม

spf[i] เก็บ smallest prime factor ทำให้แยกตัวประกอบได้เร็ว

vector<int> factorize(int n) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

Segmented Sieve

หา prime ในช่วง [L, R] เมื่อ R มีค่าสูงมาก (เช่น $10^{12}$) แต่ช่วงกว้าง R - L ไม่เกิน $10^6$

vector<long long> segmentedSieve(long long L, long long R) {
    // หา prime ถึง sqrt(R) ก่อน
    int sqrtR = sqrt(R) + 1;
    sieve(sqrtR);
    
    // สร้าง array สำหรับช่วง [L, R]
    vector<bool> is_prime(R - L + 1, true);
    
    for (int p : primes) {
        if ((long long)p * p > R) break;
        
        // หา multiple แรกของ p ที่ >= L
        long long start = max((long long)p * p, ((L + p - 1) / p) * p);
        
        for (long long j = start; j <= R; j += p) {
            is_prime[j - L] = false;
        }
    }
    
    // กรณี L = 1
    if (L == 1) is_prime[0] = false;
    
    vector<long long> result;
    for (long long i = 0; i <= R - L; i++) {
        if (is_prime[i]) result.push_back(L + i);
    }
    
    return result;
}

Prime Counting Function

$\pi(n)$ = จำนวน prime ที่ $\leq n$

ค่าประมาณ

$\pi(n) \approx \frac{n}{\ln n}$

n	$\pi(n)$	ประมาณ
$10^3$	168	145
$10^6$	78,498	72,382
$10^9$	50,847,534	48,254,942

Prime Gap

ระยะห่างระหว่าง prime ที่ติดกัน

• สำหรับ $n \leq 10^6$ gap ไม่เกิน 100
• สำหรับ $n \leq 10^9$ gap ไม่เกิน 300

Primality Testing สำหรับ Large Numbers

Miller-Rabin Primality Test

ทดสอบว่า $n$ เป็น prime หรือไม่ ใน $O(k \log^3 n)$ โดย $k$ คือจำนวนรอบทดสอบ

long long mulmod(long long a, long long b, long long m) {
    return (__int128)a * b % m;
}

long long powmod(long long a, long long b, long long m) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        b >>= 1;
    }
    return res;
}

bool millerRabin(long long n, long long a) {
    if (n % a == 0) return n == a;
    
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    
    long long x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    
    return false;
}

bool isPrimeLarge(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    
    // Witnesses สำหรับ n < 3,317,044,064,679,887,385,961,981
    vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    
    for (long long a : witnesses) {
        if (n == a) return true;
        if (!millerRabin(n, a)) return false;
    }
    
    return true;
}

Goldbach’s Conjecture

จำนวนคู่ทุกตัวที่มากกว่า 2 สามารถเขียนเป็นผลบวกของ prime สองตัวได้

pair<int, int> goldbach(int n) {
    sieve(n);
    for (int p : primes) {
        if (isPrime[n - p]) {
            return {p, n - p};
        }
    }
    return {-1, -1}; // ไม่ควรเกิดขึ้น
}

ตัวอย่างโจทย์

โจทย์ 1: นับจำนวน prime ในช่วง

int countPrimes(int L, int R) {
    sieve(R);
    int count = 0;
    for (int i = L; i <= R; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

โจทย์ 2: หา prime ตัวที่ k

int kthPrime(int k) {
    sieve(10000000); // ประมาณว่า prime ตัวที่ k อยู่ในช่วงนี้
    return primes[k - 1];
}

โจทย์ 3: หา prime factors ที่แตกต่างกัน

int countDistinctPrimeFactors(int n) {
    linearSieve(n);
    set<int> factors;
    while (n > 1) {
        factors.insert(spf[n]);
        n /= spf[n];
    }
    return factors.size();
}

สรุป

Algorithm	Complexity	ใช้สำหรับ
Basic Check	$O(\sqrt{n})$	ตรวจสอบ 1 ตัว
Sieve of Eratosthenes	$O(n \log \log n)$	หา prime ทั้งหมดถึง n
Linear Sieve	$O(n)$	หา prime + SPF
Segmented Sieve	$O((R-L) \log \log R)$	Prime ในช่วง [L, R]
Miller-Rabin	$O(k \log^3 n)$	Prime test สำหรับ n ใหญ่

💡 Tip: สำหรับโจทย์ที่ต้องใช้ prime หลายครั้ง ให้ sieve ไว้ก่อนแล้วเก็บใน vector