หา Twin Primes คู่มากที่สุดในช่วงที่กำหนดใน C++

ในปัญหานี้ เราได้รับช่วง [lValue, hValue] งานคือหา Twin Primes (คู่จำนวนเฉพาะที่ต่างกัน 2) คู่มากที่สุดในช่วงนั้น

ตัวอย่าง

Input: lValue = 65, rValue = 100 Output: 71, 73

วิธีการแก้ปัญหา: Sieve of Eratosthenes + ตรวจสอบจากขวาไปซ้าย

สร้าง boolean array primes[] ด้วย Sieve จนถึง rValue
วนลูปจาก rValue ลงมา lValue+2
เช็คว่า i และ i-2 เป็น prime ทั้งคู่หรือไม่
เจอคู่แรก = คู่มากที่สุด → หยุด

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

#include <bits/stdc++.h>
using namespace std;

void findLargestTwins(int lValue, int uValue) {
    vector primes(uValue + 1, true);
    primes[0] = primes[1] = false;
    for (int p = 2; p * p <= uValue; p++)
        if (primes[p])
            for (int i = p * 2; i <= uValue; i += p)
                primes[i] = false;
    
    int i;
    for (i = uValue; i >= lValue; i--) {
        if (primes[i] && i - 2 >= lValue && primes[i - 2]) break;
    }
    
    if (i >= lValue) cout << "Largest twins: (" << (i-2) << ", " << i << ")";
    else cout << "No Twins possible";
}

int main() {
    findLargestTwins(54, 102);
    return 0;
}

ผลลัพธ์

Largest twins in given range: (71, 73)