C++의 에라토스테네스 알고리즘의 체
이 기사에서는 C++에서 에라토스테네스의 체 알고리즘을 구현하는 방법을 설명합니다.
C++에서 std::vector 컨테이너를 사용하여 에라토스테네스 알고리즘의 체 구현
에라토스테네스의 체는 소수를 찾는 비교적 효율적인 알고리즘을 나타내는 소수 체 중 하나입니다. 서로 다른 소수 범위에 적합한 여러 알고리즘이 있으며 대조되는 성능 특성도 있습니다.
에라토스테네스의 체는 구현하기 가장 쉬운 것으로 간주될 수 있으며 더 작은 범위에서 매우 효율적입니다. 실행 시간 복잡도가 O(N loglogN)이지만 더 작은 범위에서 더 잘 수행됩니다.
이 기사에서는 입문 기사에 적합하도록 가장 간단한 방법을 사용하여 이 알고리즘을 구현합니다. 알고리즘은 정수 값을 취해 주어진 정수보다 작거나 같은 모든 소수를 찾습니다.
처음에는 주어진 정수와 크기가 같은 부울 값의 배열을 구성하고 모든 요소가 true 값을 갖도록 초기화합니다.
그런 다음 이 요소 배열을 반복하고 주어진 요소에 복합 인덱스가 있으면 false 값을 저장합니다. 가장 작은 것인 2부터 연속 소수의 배수를 계산하여 배열 인덱스에 액세스하고 주어진 소수의 제곱이 입력 정수 n보다 크면 반복을 중지합니다. 이전 단계는 printPrimesLessThanN 함수의 중첩 for 루프를 사용하여 구현됩니다.
마지막으로 이 벡터를 순환하고 true 값이 저장된 요소 인덱스를 인쇄합니다. 후자의 작업은 printPrimesLessThanN 함수 끝에 있는 for 루프에 의해 처리됩니다. 또한 main 함수에 드라이버 코드를 제공하여 사용자의 상한을 나타내는 정수를 수락하고 printPrimesLessThanN 함수에 전달될 때까지 입력을 검증합니다.
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
void printPrimesLessThanN(unsigned long long n) {
vector<bool> table(n, true);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == true) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
}
}
for (unsigned long long p = 2; p < n; p++)
if (table[p]) cout << p << " ";
}
int main() {
unsigned long long integer;
while (true) {
cout << "Enter integer: ";
if (cin >> integer) {
break;
} else {
cout << "Enter a valid integer value!\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
cout << "Following prime numbers are smaller than given integer: \n";
printPrimesLessThanN(integer);
return EXIT_SUCCESS;
}
출력:
Enter integer: 30
Following prime numbers are smaller than given integer:
2 3 5 7 11 13 17 19 23 29
이전 코드 스니펫은 프로그램의 동시성 활용, 데이터 액세스가 최적화되도록 배열을 메모리에 슬라이싱 및 저장 또는 기타 알고리즘 통찰력 사용과 같은 다양한 방법으로 최적화할 수 있는 작업 예제입니다. 그러나 큰 변경 없이 이 구현의 실행 시간을 여러 배로 절약할 수 있는 작은 통찰력이 하나 있습니다. 바로 char 벡터에 true/false 값을 저장하는 것입니다.
더 큰 숫자에 대해 여러 테스트를 실행하여 관찰할 수 있듯이 bool 유형은 char 또는 int와 같은 정수 유형보다 훨씬 더 나쁜 성능을 보입니다. 다음 코드 샘플은 printPrimesLessThanN 함수의 두 버전에 대한 간단한 벤치마크 시나리오를 보여주고 프로그램 종료 시 경과 시간을 인쇄합니다.
#include <sys/time.h>
#include <cstring>
#include <iostream>
#include <limits>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
void printPrimesLessThanN(unsigned long long n) {
vector<bool> table(n, true);
struct timeval start {};
struct timeval end {};
gettimeofday(&start, nullptr);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == true) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = false;
}
}
gettimeofday(&end, nullptr);
printf("printPrimesLessThanN1: %0.8f sec\n", time_diff(&start, &end));
}
void printPrimesLessThanN2(unsigned long long n) {
vector<char> table(n, 1);
struct timeval start {};
struct timeval end {};
gettimeofday(&start, nullptr);
for (unsigned long long p = 2; p * p < n; p++) {
if (table[p] == 1) {
for (unsigned long long i = p * p; i < n; i += p) table[i] = 0;
}
}
gettimeofday(&end, nullptr);
printf("printPrimesLessThanN2: %0.8f sec\n", time_diff(&start, &end));
}
int main() {
unsigned long long integer;
while (true) {
cout << "Enter integer: ";
if (cin >> integer) {
break;
} else {
cout << "Enter a valid integer value!\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
printPrimesLessThanN(integer);
printPrimesLessThanN2(integer);
return EXIT_SUCCESS;
}
출력:
Enter integer: 1000000000
printPrimesLessThanN1: 47.39665985 sec
printPrimesLessThanN2: 10.11181545 sec
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook