การสืบค้นความต่างสูงสุดของจำนวนเฉพาะในช่วงที่กำหนดใน C++

ในปัญหานี้ เราได้รับ Q queries ที่ประกอบด้วย 2 ค่า L และ R ภารกิจคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นความต่างสูงสุดของจำนวนเฉพาะในช่วงที่กำหนดใน C++

คำอธิบายปัญหา

ที่นี่ ในแต่ละ query เราได้รับ 2 ค่า L และ R เราต้องหาความต่างสูงสุด คือ ความต่างระหว่างจำนวนเฉพาะที่ใหญ่ที่สุดและเล็กที่สุดภายในช่วงที่กำหนด

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

Q = 2
2 45
14 16
41 0

เอาต์พุต

คำอธิบาย

สำหรับ query 1 จำนวนเฉพาะที่เล็กที่สุดในช่วงคือ 2 และใหญ่ที่สุดคือ 43 ความต่าง 43 - 2 = 41

สำหรับ query 2 ไม่มีจำนวนเฉพาะในช่วงที่กำหนด ดังนั้นผลลัพธ์คือ 0

แนวทางแก้ปัญหา

เพื่อแก้ปัญหานี้ เราจะสร้างอาร์เรย์ของจำนวนเฉพาะจนถึง 100005 ซึ่งเป็นช่วงที่กำหนด จากนั้นหาจำนวนเฉพาะตัวแรกที่มากกว่า L และจำนวนเฉพาะตัวแรกที่น้อยกว่า R และหาความต่างของพวกมัน

ตัวอย่างโปรแกรม

#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;
}

เอาต์พุต

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