[프로그래머스 lv1] 소수 찾기

문제 보기

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

프로그래머스

 

문제 해결

에라토스테네스의 체를 이용하여 해결한다.

1. 1은 제거한다.
2. 지워지지 않은 수 중에서 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 제거한다.
3. 지워지지 않은 수 중에서 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 제거한다.
4. 지워지지 않은 수 중에서  제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 제거한다.
5. (반복한다)

참고: https://wikidocs.net/21638

https://velog.io/@iamjinseo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A0%88%EB%B2%A81%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-python

2. 소수 구하기 - 에라토스테네스의 체

 

소스 코드

def solution(n):
    a = [False, False] + [True]*(n-1)
    primes = []
    
    for i in range(2, n+1):
        if a[i]:
            primes.append(i)
            for j in range(2*i, n+1, i): 
                a[j] = False
    return len(primes)