주어진 범위 사이의 소수를 생성하기 위해 에라토스테네스의 체를 구현하는 C++ 프로그램

이것은 주어진 범위 사이의 소수를 생성하기 위해 에라토스테네스의 체를 구현하는 C++ 프로그램입니다. 이 방법에서는 모든 요소가 포함된 정수 배열이 0으로 초기화됩니다.

중첩 루프 내에서 각 비 프라임 요소의 인덱스가 1로 표시된 곳이 따릅니다. 소수는 인덱스가 0으로 표시된 숫자입니다.

알고리즘

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

예시 코드

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

출력

1 2 3 5 7 11 13 17 19 23 29