Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình C ++ để thực hiện sàng lọc eratosthenes để tạo số nguyên tố giữa phạm vi đã cho

Đây là chương trình C ++ để thực hiện Sieve of Eratosthenes để tạo ra số nguyên tố giữa phạm vi đã cho. Trong phương thức này, một mảng số nguyên với tất cả các phần tử được khởi tạo bằng 0.

Nó theo sau nơi chỉ mục của mỗi phần tử không phải nguyên tố được đánh dấu là 1 bên trong các vòng lặp lồng nhau. Các số nguyên tố là những số có chỉ số được đánh dấu là 0.

Thuật toán

Begin
   Declare an array of size n and initialize it to zero
   Declare length, i, j
   Read length
   For i = 2 to n-1 do
      For j = i*i to n-1 do
         Arr[j-1]=1
      Done
   Done
   For i =1 to n do
      If(arr[i-1]==0)
         Print i
   Done
End

Mã mẫu

#include <iostream>
const int len = 30;
int main() {
   int arr[30] = {0};
   for (int i = 2; i < 30; i++) {
      for (int j = i * i; j < 30; j+=i) {
         arr[j - 1] = 1;
      }
   }
   for (int i = 1; i < 30; i++) {
      if (arr[i - 1] == 0)
         std::cout << i << "\t";
   }
}

Đầu ra

1 2 3 5 7 11 13 17 19 23 29