เราได้รับจำนวนบวก n เป็นอินพุต เป้าหมายคือการหาจำนวนคู่ที่เป็นไปได้ (i,j) โดยที่แต่ละคู่มีผลรวม (i+j) ซึ่งเป็นจำนวนเฉพาะและน้อยกว่า n นอกจากนี้ i !=j และ i,j>=1 ถ้า n เป็น 4 ดังนั้นจะมีเพียง 1 คู่เท่านั้น ซึ่งก็คือ (1,2) ที่นี่ 1+2 =3 เป็นจำนวนเฉพาะและน้อยกว่า 4 และ 1,2>=1 ด้วย
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − n=7
ผลผลิต − นับคู่ที่มีผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n คือ − 3
คำอธิบาย − คู่จะเป็น (1,2), (1,4), (2,3) ผลรวม 3, 5, 5 เป็นจำนวนเฉพาะและน้อยกว่า 7
ป้อนข้อมูล − n=10
ผลผลิต − นับคู่ที่มีผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n คือ − 6
คำอธิบาย −
คู่จะเป็น (1,2) (1,4) (2,3) (1,6) (2,5), (3,4)
ผลรวมที่ 3, 5, 5, 7, 7, 7 เป็นจำนวนเฉพาะและน้อยกว่า 10
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในวิธีนี้ เราจะค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า n โดยใช้ Sieve of Sundaram ในฟังก์ชัน check_prime(bool check[], int temp)
นอกจากนี้ สำหรับแต่ละอุณหภูมิเลขคี่ การนับของคู่ที่แตกต่างกันซึ่งมีอุณหภูมิรวมจะเป็น temp/2
ยกเว้น 2 จำนวนเฉพาะทั้งหมดเป็นเลขคี่ ดังนั้นหากเราพบจำนวนเฉพาะใดๆ ที่น้อยกว่า n เราจะบวก temp/2 เพื่อนับจำนวนคู่
-
รับตัวแปร n เป็นอินพุต
-
ฟังก์ชัน prime_pair(int n) รับ n และส่งกลับจำนวนคู่ที่มีผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n
-
นับเริ่มต้นเป็น 0
-
เนื่องจาก Sieve of Sundaram สร้างจำนวนเฉพาะน้อยกว่า 2*n+2 สำหรับอินพุต n เราลด n ลงครึ่งหนึ่งแล้วเก็บใน temp_2
-
สร้างอาร์เรย์ Check[] ของความยาว temp_2 เพื่อทำเครื่องหมายตัวเลขทั้งหมดของแบบฟอร์ม ( i+j+2*i*j ) เป็น True เริ่มต้นด้วยองค์ประกอบทั้งหมดเป็นเท็จ
-
ใช้ฟังก์ชัน check_prime(bool check[], int temp) เริ่มต้น check[] ด้วยค่าจริงสำหรับตัวเลขของแบบฟอร์ม (i+j+2*i*j) และผลรวมนี้ <ชั่วคราว
-
ตอนนี้สำรวจ [] โดยใช้ for loop จากดัชนี i=0 ถึง i
-
สำหรับแต่ละเช็ค[i] เป็นเท็จ หมายเลขเฉพาะจะเป็น temp=2*i+1
-
คู่ที่รวมกันเป็น temp จะเป็น temp/2
-
เพิ่ม temp/2 เพื่อนับ
-
ในตอนท้ายของ for loop เราจะมีคู่ทั้งหมดที่มีผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp){
for (int i=1; i<=temp; i++){
for (int j=i; (i + j + 2*i*j) <= temp; j++){
check[i + j + 2*i*j] = true;
}
}
}
int prime_pair(int n){
int count = 0;
int temp;
int temp_2 = (n-2)/2;
bool check[temp_2 + 1];
memset(check, false, sizeof(check));
check_prime(check, temp_2);
for (int i=1; i <= temp_2; i++){
if (check[i] == false){
temp = 2*i + 1;
count += (temp / 2);
}
}
return count;
}
int main(){
int n = 10;
cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of pairs with sum as a prime number and less than n are: 6
