home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Prime Triplet - ชุดจำนวนเฉพาะสามตัวใน C++

ภาพรวมปัญหา

ได้รับตัวเลข N ต้องพิมพ์ Prime Triplet ทั้งหมดที่น้อยกว่า N

Prime Triplet คือชุดจำนวนเฉพาะ 3 ตัว ที่อยู่ในรูปแบบ (p, p+2, p+6) หรือ (p, p+4, p+6)

ตัวอย่าง

Input: N = 13
Output: 5 7 11

วิธีแก้ปัญหา

  1. หาจำนวนเฉพาะทั้งหมด ≤ N ด้วย Sieve of Eratosthenes
  2. ตรวจสอบ triplet ทั้งสองรูปแบบ

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

#include <bits/stdc++.h>
using namespace std;

void findPrimes(int n, bool prime[]) {
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
}

void printPrimeTriplets(int n) {
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    findPrimes(n, prime);
    for (int i = 2; i <= n - 6; ++i) {
        if (prime[i] && prime[i + 2] && prime[i + 6])
            cout << i << "\t" << (i+2) << "\t" << (i+6) << endl;
        else if (prime[i] && prime[i + 4] && prime[i + 6])
            cout << i << "\t" << (i + 4) << "\t" << (i + 6) << endl;
    }
}

int main() {
    int N = 15;
    cout << "Prime Triplets Less than " << N << " are :\n";
    printPrimeTriplets(N);
    return 0;
}

ผลลัพธ์

Prime Triplets Less than 15 are : 5  7  11
7  11  13