에라토스테네스의 체

프로그래머스 소수 찾기 문제를 풀다가 최적의 알고리즘을 찾기 시작했다. 내가 푸는 방법으로는 실패가 떠서 찾기 시작했다. 에라토스테네스의 체 (Sieve of Eratosthenes) 라는 알고리즘을 공부 해보도록 하겠다. 위키백과에 설명이 잘 되어있다. 위의 그림처럼 1부터 120 사이에 소수를 구해보자! 소수는 1과 자기 자신으로만 나누어지는 수를 의미한다. ( 1은 소수가 아니다.) 2부터 120까지 표에 적어넣고 소수가 아닌것을 모두 체크 한다. 2는 소수이다. 그럼 2의 배수를 체크한다. 3은 소수이다. 그럼 3의 배수를 체크한다. 4는 2의 배수에서 체크했으니깐 제외 5는 소수이다. 그럼 5의 배수를 체크한다. 6은 2의 배수에서 체크했으니깐 제외 ........ 체크가 안된 수들이 소수이다...