Tìm cặp song sinh lớn nhất trong phạm vi đã cho trong C ++

Trong bài toán này, chúng ta được cung cấp hai giá trị lValue và hValue. Nhiệm vụ của chúng tôi là tìm cặp song sinh lớn nhất trong phạm vi đã cho .

Hai số được cho là số sinh đôi nếu cả hai đều là số nguyên tố và hiệu của chúng là 2.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là lặp lại từ rValue - 2 đến lValue và kiểm tra từng cặp i và (i + 2) để tìm cặp song sinh và in ra cặp song sinh xuất hiện đầu tiên.

Cách tiếp cận khác là tìm tất cả các số nguyên tố trong phạm vi và sau đó kiểm tra cặp i và (i + 2) lớn nhất là số nguyên tố và

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <bits/stdc++.h>
using namespace std;
void findLargestTwins(int lValue, int uValue) {
   bool primes[uValue + 1];
   memset(primes, true, sizeof(primes));
   primes[0] = primes[1] = false;
   for (int p = 2; p <= floor(sqrt(uValue)) + 1; 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] == true)) {
         break;
      }
   }
   if(i >= lValue )
      cout<<"Largest twins in given range: ("<<(i-2)<<", "<<i<<")";
   else 
      cout<<"No Twins possible";
}
int main(){
   int lValue = 54;
   int uValue = 102;
   findLargestTwins(lValue, uValue);
   return 0;
}

Đầu ra

Largest twins in given range: (71, 73)