Tìm cặp số sinh đôi lớn nhất trong khoảng cho trước C++

Cho hai giá trị lValue và hValue. Nhiệm vụ: tìm cặp số sinh đôi lớn nhất trong khoảng. Số sinh đôi = cả hai đều là số nguyên tố và hiệu bằng 2.

Ví dụ minh họa

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

Phương pháp giải

Sàng Eratosthenes tìm tất cả số nguyên tố trong khoảng. Duyệt từ hValue xuống lValue, kiểm tra cặp (i-2, i) đều là số nguyên tố.

Ví dụ chương trình

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

void findLargestTwins(int lValue, int uValue) {
    vector<bool> 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 << "Cặp sinh đôi lớn nhất: (" << (i-2) << ", " << i << ")";
    else
        cout << "Không có cặp sinh đôi";
}

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

Kết quả

Cặp sinh đôi lớn nhất: (71, 73)