수학과의 좌충우돌 프로그래밍

[C++] 최적의 소수찾기, 에라토스테네스의 체

안녕하세요 강민성입니다. 이번 포스팅에서는 소수를 찾는 방법에 대해서 알아보도록 하겠습니다. 소수를 찾는 방법이 여러가지가 있지만 그 중에 가장 효율이 좋은 '에라토스테네스의 체' 에 대해서 알아보도록 합시다. 최적의 소수 찾기, 에라토스테네스의 체 먼저 동영상을 보고 어떠한 원리로 소수를 찾는지 보도록 하겠습니다. 2부터 120까지 수 중 소수를 판별한다고 해보겠습니다. 다음과 같은 알고리즘으로 소수를 찾게 됩니다. 1. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들은 소수가 아니므로 체크한다. 2. 다음 숫자를 확인하여 체크가 안되있으면 그 수를 오른쪽에 쓰고 그 수의 배수들은 체크, 체크가 되어있으면 다음 수로 넘어간다. 3. 120의 제곱근까지 다음 과정을 반복한다. 이 알고리즘을 이제 C++ ..

알고리즘/C++ 2019. 2. 8. 14:00