Truy vấn hiệu lớn nhất giữa các số nguyên tố trong khoảng cho trước trong C++

Trong bài toán này, ta được cho Q truy vấn, mỗi truy vấn gồm hai giá trị L và R. Nhiệm vụ là tạo chương trình giải quyết: truy vấn hiệu lớn nhất giữa các số nguyên tố trong các khoảng cho trước trong C++.

Mô tả bài toán: Ở mỗi truy vấn, cho hai giá trị L và R. Cần tìm hiệu lớn nhất, tức hiệu giữa số nguyên tố lớn nhất và nhỏ nhất trong khoảng cho trước.

Ví dụ minh họa

Đầu vào

Q = 2
2 45
14 16
41 0

Đầu ra

Giải thích

Truy vấn 1: số nguyên tố nhỏ nhất trong khoảng là 2, lớn nhất là 43. Hiệu = 43 - 2 = 41.

Truy vấn 2: không có số nguyên tố nào trong khoảng, kết quả = 0.

Phương pháp giải

Để giải bài toán, ta tạo mảng đánh dấu số nguyên tố đến 100005 (giới hạn đề bài). Sau đó tìm số nguyên tố đầu tiên ≥ L và số nguyên tố cuối cùng ≤ R, lấy hiệu của chúng.

Chương trình minh họa:

Ví dụ

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

bool primeNumber[100005];

void findPrimes() {
    memset(primeNumber, true, sizeof(primeNumber));
    for (int i = 2; i * i < 100005; i++) {
        if (primeNumber[i]) {
            for (int j = i + i; j < 100005; j += i)
                primeNumber[j] = false;
        }
    }
}

int findPrimeInRange(int L, int R) {
    int LPrime = 0;
    int RPrime = 0;
    for(int i = L; i <= R; i++) {
        if(primeNumber[i] == true) {
            LPrime = i;
            break;
        }
    }
    for(int j = R; j >= L; j--) {
        if(primeNumber[j] == true) {
            RPrime = j;
            break;
        }
    }
    return (RPrime - LPrime);
}

int main() {
    int Q = 3;
    int query[Q][2] = {{4, 15}, {32, 37}, {54, 1100}};
    findPrimes();
    for (int i = 0; i < Q; i++)
        cout << "For query " << (i+1) << ": The maximum difference between primes numbers is "
             << findPrimeInRange(query[i][0], query[i][1]) << "\n";
    return 0;
}

Đầu ra

For query 1: The maximum difference between primes numbers is 8
For query 2: The maximum difference between primes numbers is 0
For query 3: The maximum difference between primes numbers is 1038