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

<정답>

import math

def solution(n):
    answer = 0
    for i in range (2, n+1):
        check_prime = True
        for j in range(2, int(math.sqrt(i))+1):
            if(i % j == 0):
                check_prime = False
                break
        if(check_prime):
            answer += 1
    return answer

for j in range(2, i+1)

시간초과로 실패

 

-> 제곱근까지 돌리니까 문제 해결됨(시간복잡도 감소)

 

의문: 어차피 제곱근 넘어서 가기 전에 break로 끊기는데도 시간초과가 뜨는 이유가 뭘까?

-> 엄청 큰 소수를 돌릴 때 제곱근까지만 돌려도 되는데 구지 n까지 돌릴 이유가 없기 때문

 

<피드백 후>

import math

def solution(n):
    answer = 0
    for i in range (2, n+1):
        prime = True
        for j in range(2, int(math.sqrt(i))+1):
            if i % j == 0 :
                prime = False
                break
        if prime:
            answer += 1
    return answer

고친점

- if 문 뒤에 괄호 없어도 됨

- check_prime보다 prime인 경우 'if prime' 이 돼서 더 보기 좋음