Thuật toán nào nhanh nhất để tìm số nguyên tố bằng C ++?

Sieve of Eratosthenes là một trong những cách hiệu quả nhất để tìm các số nguyên tố nhỏ hơn n khi n nhỏ hơn khoảng 10 triệu.

Một chương trình thể hiện Sieve of Eratosthenes được đưa ra như sau.

Ví dụ

#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;
}

Đầu ra

Kết quả của chương trình trên như sau.

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

Bây giờ, chúng ta hãy hiểu chương trình trên.

Hàm SieveOfEratosthenes () tìm tất cả các số nguyên tố xuất hiện trước num được cung cấp dưới dạng đối số. Đoạn mã cho điều này được đưa ra như sau.

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 << " ";
}

Hàm main () đặt giá trị của num và sau đó in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng num. Điều này được thực hiện bằng cách gọi hàm SieveOfEratosthenes (). Đoạn mã cho điều này được đưa ra như sau.

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