อัลกอริธึมใดเร็วที่สุดในการค้นหาจำนวนเฉพาะโดยใช้ C++

ตะแกรงของ Eratosthenes เป็นหนึ่งในวิธีที่มีประสิทธิภาพมากที่สุดในการค้นหาจำนวนเฉพาะที่น้อยกว่า n เมื่อ n น้อยกว่า 10 ล้านตัว

โปรแกรมที่สาธิต Sieve of Eratosthenes มีดังนี้

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int num) {
   bool pno[num+1];
   memset(pno, true, sizeof(pno));
   for (int i = 2; i*i< = num; i++) {
      if (pno[i] == true) {
         for (int j = i*2; j< = num; j + = i)
         pno[j] = false;
      }
   }
   for (int i = 2; i< = num; i++)
   if (pno[i])
   cout << i << " ";
}
int main() {
   int num = 15;
   cout << "The prime numbers smaller or equal to "<< num <<" are: ";
   SieveOfEratosthenes(num);
   return 0;
}

ผลลัพธ์

ผลลัพธ์ของโปรแกรมข้างต้นมีดังนี้

The prime numbers smaller or equal to 15 are: 2 3 5 7 11 13

ตอนนี้ เรามาทำความเข้าใจโปรแกรมข้างต้นกัน

ฟังก์ชัน SieveOfEratosthenes() จะค้นหาจำนวนเฉพาะทั้งหมดที่เกิดขึ้นก่อน num ที่ระบุเป็นอาร์กิวเมนต์ ข้อมูลโค้ดสำหรับสิ่งนี้มีดังต่อไปนี้

void SieveOfEratosthenes(int num) {
   bool pno[num+1];
   memset(pno, true, sizeof(pno));
   for (int i = 2; i*i< = num; i++) {
      if (pno[i] == true) {
         for (int j = i*2; j< = num; j + = i)
         pno[j] = false;
      }
   }
   for (int i = 2; i< = num; i++)
   if (pno[i])
   cout << i << " ";
}

ฟังก์ชัน main() ตั้งค่าของ num แล้วพิมพ์จำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ num ทำได้โดยการเรียกใช้ฟังก์ชัน SieveOfEratosthenes() ข้อมูลโค้ดสำหรับสิ่งนี้มีดังต่อไปนี้

int main() {
   int num = 15;
   cout << "The prime numbers smaller or equal to "<< num <<" are: ";
   SieveOfEratosthenes(num);
   return 0;
}