นับคู่ของตัวเลขที่ผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n ใน C++

เราได้รับจำนวนเต็มบวก n เป็นอินพุต เป้าหมายคือหาจำนวนคู่ที่เป็นไปได้ (i, j) ที่ผลรวม (i+j) เป็นจำนวนเฉพาะและน้อยกว่า n โดยที่ i != j และ i, j >= 1 หาก n เป็น 4 จะมีเพียง 1 คู่คือ (1,2) เพราะ 1+2 = 3 เป็นจำนวนเฉพาะและน้อยกว่า 4

มาดูตัวอย่าง

อินพุต − 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 จำนวนคู่ที่ต่างกันซึ่งมีผลรวมเป็น temp จะเท่ากับ temp/2

ยกเว้น 2 จำนวนเฉพาะทั้งหมดเป็นจำนวนคี่ ดังนั้นหากเราพบจำนวนเฉพาะน้อยกว่า n เราจะบวก temp/2 เข้ากับจำนวนคู่

• รับตัวแปร n เป็นอินพุต
• ฟังก์ชัน prime_pair(int n) รับ n และคืนจำนวนคู่ที่ผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n
• กำหนด count เริ่มต้นเป็น 0
• เนื่องจาก Sieve of Sundaram สร้างจำนวนเฉพาะน้อยกว่า 2*n+2 สำหรับอินพุต n เราลด n เหลือครึ่งหนึ่งเก็บใน temp_2
• สร้างอาเรย์ Check[] ความยาว temp_2 เพื่อทำเครื่องหมายตัวเลขรูปแบบ (i+j+2*i*j) เป็นจริง เริ่มต้นทั้งหมดเป็นเท็จ
• ใช้ฟังก์ชัน check_prime(bool check[], int temp) ทำเครื่องหมาย check[] เป็นจริงสำหรับตัวเลขรูปแบบ (i+j+2*i*j) และผลรวม < temp
• เดินทางผ่าน Check[] ด้วยลูป for จากดัชนี i=0 ถึง i<temp_2
• สำหรับแต่ละ check[i] ที่เป็นเท็จ จำนวนเฉพาะจะเป็น temp=2*i+1
• คู่ที่รวมกันได้ temp จะเป็น temp/2
• บวก temp/2 เข้า count
• ในท้ายที่สุดของลูป เราจะได้จำนวนคู่ทั้งหมดที่ผลรวมเป็นจำนวนเฉพาะและน้อยกว่า n
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด C++

#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