[백준][python][4948] 에라토스테네스의 체

[문제]

[출처 및 링크]

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

[어떻게 풀까?]

이 문제는 에라스토테네스의 체를 이용해야 풀 수 있다. 이것을 써야 시간 복잡도가 작아지기 때문이다. 에레스토테네스의 체에 대한 개념은 다음 그림과 같다.

만약 2가 소수라면 2의 배수에 해당하는 수들을 모두 지워준다. 만약 3이 소수라면 3의 배수에 해당하는 수들을 모두 지워준다. 그렇게 되면 남은 수들은 모두 소수라는 이야기 이다. 이것을 코드로 구현하기 위해서는 수의 범위가 정해져 있어야 한다. 한 번 코드를 작성해 보자.

[코드]

 

start, end = map(int, input().split())
array = [0]*(end+1)

for i in range(2, end+1):
    if array[i]==0:
        if i>=start:
            print(i)
        j= 1
        while i*j<=end:
            array[i*j] = 1
            j +=1

 

[설명]

나는 start와 end라는 변수를 정해주어서 범위를 지정해 주었다. 이런식으로 범위를 지정해 주면 그에 맞는 배열을 정의해준다.

배열은 모두 0으로 초기화 해준다. True, False로 해도 될 것 같다. 하지만 나는 0, 1이 더 취향에 맞아서 이렇게 하였다. 

돌아와서, 2부터 소수이기 때문에 for문은 2부터 시작해 주었다. 배열이 0이라는 것은 그 수가 소수임을 의미한다. 왜냐하면 소수의 배수는 내가 모두 지워주었기 때문이다. 그리고 if 문을 통해 start보다 큰 값만 출력하게 만들어 주었다. while문은 소수의 배수를 지워주는 과정이다. for문을 써도 될 듯하다. 

 

사실 이 문제를 푼 이유는 뒤의 골드바흐의 추측을 더 효과적으로 풀기 위해서이다. 만약 골드바흐의 추측을 풀지 않았다면 이것을 토대로 진행해 보는 것을 추천한다.