พิมพ์จำนวนเฉพาะทั้งหมดที่มีจำนวนน้อยกว่าใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวก N และเราต้องพิมพ์ allprime quadruplet น้อยกว่าหรือเท่ากับ n

ไพรม์สี่เท่า คือเซตของจำนวนเฉพาะสี่จำนวนที่คำนวณได้เป็น {p, p ⁺² ,p ⁺⁶ , p ⁺⁸ }. ตัวอย่าง − 5 7 11 13.

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −

Input: N = 15
Output: 5 7 11 13.

ในการแก้ปัญหานี้ วิธีง่ายๆ คือการสร้างสี่เท่าของจำนวนเฉพาะ p และตรวจสอบว่า p ทั้งหมด p ⁺² , p ⁺⁶ , p ⁺⁸ เป็นจำนวนเฉพาะ วิธีแก้ปัญหานี้ง่ายแต่ซับซ้อนกว่าสำหรับคอมไพเลอร์

วิธีที่มีประสิทธิภาพอีกวิธีหนึ่งคือการชื่นชอบจำนวนเฉพาะทั้งหมด (โดยใช้ตะแกรงของ Eratosthenes) และจัดเก็บไว้ในอาร์เรย์จนถึงช่วงที่กำหนด และสำรวจอาร์เรย์และตรวจสอบ p, p ⁺² , p ⁺⁶ , p ⁺⁸ เป็นไพรม์หรือไม่และพิมพ์ว่าทั้งหมดเป็นไพรม์หรือไม่

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
bool prime[MAX];
void primeNumberGenerator() {
   memset(prime, true, sizeof(prime));
   for (int p = 2; p * p < MAX; p++) {
      if (prime[p] == true) {
         for (int i = p * 2; i < MAX; i += p)
            prime[i] = false;
      }
   }
}
void printPrimeQuadruplet(int n) {
   for (int i = 0; i < n - 7; i++) {
      if (prime[i] && prime[i + 2] && prime[i + 6] && prime[i + 8]) {
         cout<<i<<" "<<i+2<<" "<<i+6<<" "<<i+8<<endl;
      }
   }
}
int main() {
   primeNumberGenerator();
   int n = 42;
   cout<<"All prime Quadruplets are :\n";
   printPrimeQuadruplet(20);
   return 0;
}

ผลลัพธ์

ไพรม์ควอดเล็ตทั้งหมดคือ −

5 7 11 13
11 13 17 19