[프로그래머스][Lv.0] 합성수 찾기

문제

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

프로그래머스

 

내 풀이

def solution(n):
    # n 이하 소수의 개수 찾기
    # n - 소수 개수 - 1(1은 약수가 1이니까)
    prime_list = []
    for i in range(2, n+1):  # 수정된 부분
        for prime in prime_list:
            if prime > i**0.5:  # 정답 후 추가된 부분
                prime_list.append(i)  
                break
            if i % prime == 0:
                break
        else:
            prime_list.append(i)
            
    return n - len(prime_list) - 1

처음에 범위를 range(2, n)으로 잡아 n을 포함시키지 못해 정답을 못찾았는데

수정 후 정답이 되는 것을 확인.

추가로, 단순히 소수 list 전체를 확인해 소수 여부를 확인하는 과정에서

대상 i의 제곱근보다 비교하는 소수가 커지면 i는 소수인 점을 이용해 연산 속도를 더 높였다.