C++를 사용하여 소수를 찾는 가장 빠른 알고리즘은 무엇입니까?

에라토스테네스의 체는 n이 약 1천만보다 작을 때 n보다 작은 소수를 찾는 가장 효율적인 방법 중 하나입니다.

에라토스테네스의 체를 보여주는 프로그램은 다음과 같습니다.

예시

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