[algorithm][python] 프로그래머스 소수찾기

문제

소수 찾기

처음에 작성한 코드

 def solution(n):
     num_of_prime = 0
     for num in range(2, n+1):
         is_prime = True
         
         for divisor in range(2, num//2+1):
             if num % divisor == 0:
                 is_prime = False
                 break
                
         if is_prime:
             num_of_prime += 1
        
     return num_of_prime

위와 같이 풀었는데 시간초과가 떴다.
조건에 따르면 n은 2이상 1000000이하의 자연수이다.
n이 최대 백만 정도로, 단순 반복으로 풀기에는 복잡도가 O(n^2)이 되어 시간초과가 발생한 것 같다.

문제점 및 해결방안

이 블로그(이미지, 알고리즘의 출처)를 참고했고 에라토스테네스의 체 방법을 사용해서 해결했다.

알고리즘

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

그림의 경우 11² >120 이므로 11보다 작은 배수들만 지워도 충분하다.

최종 코드

 def solution(n):
     nums = [False,False] + [True]*(n-1) # 0, 1 제외 나머지 소수로 간주
     for i in range(2, int(n ** 0.5)+1): # 2부터 n의 제곱근(n의 최대 약수가 n의 제곱근 이하)까지의 모든 수를 확인하며 소수를 검사
         if nums[i]: # i가 소수인 경우
             for j in range(2*i, n+1, i): # i이후 i의 배수를 모두 소수에서 제거(False)
                 nums[j] = False
     return nums.count(True)