[프로그래머스] 소수 찾기 - 파이썬

Programmers

소수 찾기

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

프로그래머스

문제

코드

• 시간 초과 코드
• 전체 약수 개수를 계산한 다음에 약수가 2개인 것을 더하는 방법은 시간초과

def solution(n):
    answer = 0
    lst = []

    for i in range(1, n+1):
        count = 0
        for j in range(1, int(i**0.5)+1):
            if i % j == 0:
                if j ** 2 == i:
                    count += 1
                else:
                    count += 2 
        if count == 2:
            answer += 1

    return answer

 

• 시간 초과를 해결하기 위해서는 에라토스테네스의 체 방식을 사용해야함.
• 에라토네스의 체: n까지의 소수를 구할 때
  • 2를 제외한 모든 2의 배수를 제거
  • 3을 제외한 모든 3의 배수를 제거
  • 5를 재외한 모든 5의 배수를 제거
  • ....  

def solution(n):
    num = set(range(2,n+1))
    
    for i in range(2,n+1):
        if i in num:
            num -= set(range(2*i,n+1,i))
    return len(num)