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

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

코딩테스트 연습 - 소수 찾기

소수 찾기는 주어진 수가 소수인가 를 판별할떄는 단순하게 for문을 이용한 풀이를 떠올릴 수 있다.

근데 에라토스테네스의 체 방법을 이용하면 주어진 수까지의 모든 수의 소수여부를 판단할 수 있고 효율성문제를 해결할 수 있다. 에라토스테네스의 체 원리를 살펴보자.

 

애라토스테네스의 체 : 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

1. 2부터 N까지 모든 수를 prime 배열에 추가한다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. (2가 가장 작은수임)
3. 그 수는 소수이다. (2는 소수다)
4. 이제 그 수의 배수를 모두 지운다. (2의 배수를 모두 지운다)
5. 다시 지워지지 않은 수 중에서 가장 작은수를 찾는다 (이제 3이 가장 작은수임)
6. 반복

이렇게해서 prime배열에 추가된 모든수가 소수가 된다.

 

내 코드

 

def prime_count(n):
    prime = []
    check = [0 for _ in range(n+1)]
    
    for i in range(2, n+1):
        if check[i] == 0:
            prime.append(i)
            for j in range(i*i, n+1, i):
                check[j] = 1
    return len(prime)


def solution(n):
    return prime_count(n)