[프로그래머스] Lv.1 소수 찾기

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

프로그래머스

 

 

1. 해결방법

이 문제는 소수를 찾기 위해서 2중 for문을 사용해서 접근하였다.
하지만 방문체크와 같은 If 분기문을 사용해서 for문 안에서 케이스를 줄여나가지 않으면 반드시 시간 초과가 걸리게 되어있다. 
참고로 이 문제의 시간 복잡도는 10^6 이기에 2중 for문을 그대로 쓸 경우에 시간복잡도부터 에러이다.

본인도 몰랐지만 '에라토스테네스의 체' 라는 알고리즘 방법을 사용하면 된다.

1. 방문 체크를 위한 n + 1개 만큼의 False가 담긴 배열을 생성한다.
2. 방문 체크 배열의 i 인덱스 값이 False인 경우에 소수인지 체크하고 그 i값은 소수이므로 answer += 1
3. 소수인 i를 (n + 1)만큼 i 간격으로 for문을 한번 더 돌려서 소수가 아닌 숫자를 방문 체크 (j)를 한다.
4. 소수가 아닌 값들은 chk[j]를 True로 바꾸며 2중 for문을 돌린다.

 

 

2. 정답코드

def solution(n):
    answer = 0
    chk = [False] * (n + 1)
    
    for i in range(2, n + 1):
        if chk[i] == False:
            answer += 1
            for j in range(i, n + 1, i):
                chk[j] = True
            

    return answer

이 문제의 핵심은 시간초과가 나지 않으면서 2중 for문을 사용하면 된다.

물론 2중 for문을 안써도 되겠지만 본인은 아직 실력 이슈라서 그렇게 해야한다.

2중 for문은 에라토스테네스의 체를 사용하면 2중 for문이라도 분기문을 이용해서 시간 복잡도를 줄일 수 있다.