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

프로그래머스 소수찾기 문제.

그냥 for 문 두개를 써서 자신보다 작은수로 일일히 나누면 시간초과가 나는 문제.

에라토스테네스의 체 알고리즘을 사용해서 푼다.

 

참고사이트(언어별 알고리즘 구현까지 있다)

 

1. 에라토스테네스의 체의 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. 
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8 .남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

2. python code

 

1. 맨 처음엔 모든 수가 소수라고 가정하고 True로 설정해 놓는다.
2. m = int(n ** 0.5) : 현재 1부터 100까지 숫자 중, m의 배수가 있는지 확인 후, m의 배수라면 소수에서 지워줘야하기 때문에 m을 지정해준다.
   예를들이 100 이하의 소수를 찾을 때, 루트100 == 10 이므로 2 ~ 10 의 배수들을 지워준다. 10까지 하는 이유는 11 이상 수의 배수는 100을 넘어가기 때문이다.(그러므로 루트를 씌워서 한도를 찾는 것이다.)
3. 이후 2 ~ m 까지 for문을 돌리면서 만약 그 수가 True이면, 그 수의 배수들을 False로 바꿔준다.