ในปัญหานี้ เราได้รับค่าสองค่า lValue และ hValue งานของเราคือ ค้นหาฝาแฝดที่ใหญ่ที่สุดในช่วงที่กำหนด .
ตัวเลข 2 ตัวจะเป็นเลขคู่หากทั้งสองจำนวนเป็นจำนวนเฉพาะและผลต่างระหว่างตัวเลขทั้งสองคือ 2
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : lValue = 65, rValue = 100 Output : 71, 73
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการวนลูปจาก rValue - 2 ถึง lValue แล้วตรวจสอบแต่ละคู่ของ i และ (i+2) เพื่อหาฝาแฝดและพิมพ์แฝดที่เกิดครั้งแรก
แนวทางอื่น คือการหาจำนวนเฉพาะทั้งหมดในช่วงนั้นแล้วตรวจสอบหาคู่ที่ใหญ่ที่สุดของ i และ (i+2) ที่เป็นจำนวนเฉพาะและ
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
Largest twins in given range: (71, 73)
