programmers - 소수찾기[level1] - python (에라토스테네스의 체)

소수찾기 문제는 알고리즘 문제 중에 기본 중에 기본이다. 이번에 정말 오랜만에 Programmers에 가서 소수찾기라는 문제를 풀면서 좀 헤멘부분이 있어서 공부할겸 블로그에 다시 정리 해보도록 한다. 에라토스테네스의 체를 설명하자면, 소수를 찾는 방법 중 하나이다. 간단하게 설명하자면, 소수들의 배수를 지워나가면서 검증 방식을 최소화 시킨 방법이다. -> 소수들의 배수들은 소수가 될수없으니까 좀 자세히 설명을 덧붙이자면, 2부터 검증을 할시(0과 1은 소수가 아니니까.) 2는 소수이니 2는 따로 빼놓고 2를 제외한 2의 배수들(2, 4, 6, 8, ...)을 소수여부를 검증(제외)한다. 3은 소수이니 3은 따로 빼놓고 3을 제외한 3의 배수들(3, 9, 15, 21, ...)을 소수여부를 검증(제외)한다..