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

문제

문제 설명

• 1 부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만든다.
• 여기서 소수는 1과 자기 자신으로만 나누어지는 수를 의미 (1은 소수가 아님)
  
  

제한 조건

• n은 2이상 1000000이하의 자연수

 

입출력 예시

• 입출력 예 #1
  • 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
• 입출력 예 #2
  • 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

 

풀이

이 문제는 입력받은 수 n에 대하여 1과 n 사이에 소수가 몇개 존재하는지 찾는 문제입니다.
처음 이 문제를 보고 레벨 1의 문제이기도 하고, 2 부터 n 까지의 수가 소수인지를 하나하나 알아보면 된다고 판단을 했습니다.
그래서 이중 for문을 이용하여 i번째의 수를 2부터 i-1까지의 수로 나누어지는지 확인 후 나누어지면 flag값을 1증가 시키고, flag 값이 0인 경우에만 answer의 값을 증가시키는 방식으로 풀이를 진행하였습니다.

def solution(n):
    answer = 1                       # 2는 소수이므로 2인 경우를 계산하여 초기값 1
    
    for i in range(3,n+1):          # 3부터 n까지의 수를 2부터 i-1까지의 수로 나누어줌
        flag = 0
        for j in range(2,i):
            if(i%j == 0):           # 나머지가 0인 경우는 나누어지는 경우
                flag = 1            # flag값 1 올려서 소수가 아님을 표시
                break
        if(flag == 0):              # flag값 0인 경우 소수임(answer+1)
            answer +=1
    return answer

이렇게 풀이를 진행하고 당연히 쉽게 해결이 될 줄 알았지만......

다음과 같이 일부 테스트 케이스와 효율성 테스트에서 모두 시간초과가 되는 문제가 발생했습니다.
생각을 해봐도 어떻게 풀어야 할지 감이 잘 잡히지 않아 소수를 찾는 시간을 줄일 수 있는 방법이 있을까 검색을 해보던 중, 에라토스테네스의 체를 이용하여 소수를 찾을 수 있다는 것을 알게되었습니다.

💡 에라토스테네스의 체

 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다.
2부터 시작하여 찾고자하는 범위의 모든 수를 나열하여, 소수인 수가 발견될 때마다, 해당 수의 배수를 모두 지우는 방식으로 소수를 찾을 수 있습니다.

이 방법을 이용하여 소스코드를 구현해보면 for문을 이용하여 2 부터 n까지의 수를 순회하는 동안 i 번째의 수가 소수인 경우(True) for문을 이용하여 i의 배수를 모두 False로 바꾸어주고, 모든 수를 순회한 후 리스트의 값이 True 일때 결과값을 1씩 증가시켜주면 됩니다. 소스코드는 아래와 같습니다.

def solution(n):                         #에라토스테네스의 체 이용
    answer = 0
    isPrime = [True] * (n+1)             # 모든 수가 소수라 가정하고 True로 초기화 
    for i in range(2, n+1):              
        if isPrime[i] == True:            # 2부터 시작해서 소수일 경우
            for j in range(i+i,n+1,i):    # 해당 소수의 배수는 자동으로 소수가 될 수 없다
                isPrime[j] = False
    
    for i in range(2,n+1):
        if(isPrime[i] == True):          # 소수일 경우 count 해서 answer 리턴
            answer +=1
    return answer

다음과 같이 모든 테스트를 통과하는 것을 확인할 수 있습니다.
Lv.1 문제이고 단순히 소수를 구하는 문제라서 만만히 보고 풀었는데, 예상한 것 보다 꽤나 많은 시간을 쓴 문제였던 것 같습니다 ㅜㅜ