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

문제 링크 (Level 1)

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

나의 코드1 (Python) - 시간초과

def solution(n):
    answer = 0
    for i in range(2, n+1): # n까지
        for j in range(2, i): # 소수찾기
            if i % j == 0: # 나머지가 0이 있으면 소수가 아님
                break
        else: # for가 끝까지 돌았다면 그 수는 소수
            answer += 1    
    return answer

해당 문제를 2중for문으로 해결하였습니다. 하지만 이는 제한조건 n은 2이상 1000000이하의 자연수입니다 

이는 위 빨간 조건에서 n값이 클수록 시간초과에 걸리게 됩니다.

시간 초과

 

나의 코드2 (Python) - 정답

def solution(n):
    answer = 0
    ch = [0]*(n+1)
    for i in range(2, n+1): # n까지
        if ch[i] == 0:
            answer += 1
            for j in range(i, n+1, i): # 소수찾기
                ch[j] = 1
                
    return answer

시간 초과를 해결하기 위해 '에라토스테네스 체' 방식을 사용하였습니다.

1. 먼저 검증할 숫자를 담을 배열을 만들어줍니다. [0] * (n+1)

2. 배열의 값이 0인 경우는 소수라고 판단하고 카운팅 합니다.

3. 2중 for문에서는 소수라고 판단했던 수의 배수들을 전부 1로 체크해줍니다.

4. 이렇게 한다면 2중 for문을 돌리는 횟수를 크게 줄일 수 있습니다.

 

효율성 통과