C에서 ++최적의 짝수 찾는 알고리즘은 무엇인가?

Eratosthenes 스크린은 n이1000만 대에 도달할 때까지 n보다 작은 소수를 찾는 가장 효율적인 방법 중 하나입니다.

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