문제 1929
> 소수 구하기 풀이
에라토스테네스의 체로 풀어 봅시다.문제를 풀기 전 에라토스테네스의 체 에 대한 정의부터 알고 가야한다.
에라토스테네스의 체 란?
가장 대표적인 소수(Prime Number) 판별 알고리즘으로 마치 체처럼 걸러낸다고 하여 이름이 붙여졌다. 대량의 소수들을 한꺼번에 판별해서 빠르고 정확하게 구현할 경우 사용한다.
[참고] 에라토스네스의 체
- 일반적 방법 : 해당 숫자를 (2 ~ 해당숫자 -1)번째 수로 차례대로 나눠 풀이
- 에라토스테네스의 체 : (2 ~ 해당숫자)범위 숫자에서 배수를 모두 지우고 남는 숫자가 소수
소수 i를 발견할 때마다 해당하는 i의 그 다음 큰 배수 부터 모두 걸러낸다.
(소수가 아닌 수는 1로 초기화하여 풀이) 이때 남는 숫자가 소수
채점 중에 100% 에 거의 다 도달해서 틀렸습니다. 가 떠서 확인해보니 또 1이 출력된 것.. 1을 제외시켜야한다.