프로그래머스 / 코딩 테스트 / 소수 찾기

문제 설명

 

 

문제 해결

 

소수를 구하는 방법으로 에라토스테네스의 체를 찾았다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

2부터 입력받은 숫자, n까지 숫자들이 소수인지 검증한다.

 

위키독스

 

def solve(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)
    

def solution(n):
    answer = solve(n)
    return answer