[python] 1929. 소수 구하기

• 문제

---

---

 

• 잘못된 풀이

M, N = map(int, input().split())

prime_list = []
for i in range(M, N+1):
    check = 0
    if i == 1:
        continue
    for j in range(2, i):
        if i % j == 0: # 나누어 떨어지면 소수아님
            check = 1
            break
    if check == 0: # 0이면 소수
        prime_list.append(i)

for i in prime_list:
    print(i)

 

해당 문제도 소수를 구하는 문제이다.

앞서 포스팅했던 두 문제 역시 '소수 구하기'에 대한 문제였기 때문에, 해당 문제도 동일한 알고리즘으로 풀고자 하였다.

 

해당 문제에 대한 풀이는 올바르다고 생각하지만, '시간초과' 문제로 문제풀이에 실패하였다.

아무래도 이중 for문을 돌면서 시간초과가 나는 것으로 판단된다.

 

 

 

• 올바른 풀이

import sys
M, N = map(int, sys.stdin.readline().split())

prime_list = []
for i in range(M, N+1):
    condition = True
    if i == 1:
        continue
    # 소수인지 판별할 때, 2-i까지 검사하는 것이 아니라 i의 제곱근까지만 검사하면 됨
    for j in range(2, int(i**0.5)+1):
        if i % j == 0: # 나누어 떨어지면 소수아님
            condition = False
            break
    if condition: # 0이면 소수
        prime_list.append(i)
print(*prime_list, sep='\n')

# 에라토스테네스의 체 풀이방법
n,m = map(int,input().split())

for i in range(2,int(m**0.5)+1):
	if prime_list[i]:
		for j in range(i*2,m+1,i):
			prime_list[j] = False

 

 

때문에 소수를 구하는 문제 풀이로 다른 방법을 모색해야 한다.

범위 내에서 소수를 판단하는 효율적인 방법론으로 '에라토스테네스의 체'가 있다.

에라토스테네스의 체를 통해 소수를 구하면 N이 5,000,000일 때 0.4초가 소요되며,

for문으로 구하는 방법에 비해 굉장히 빠르고 효율적인 알고리즘으로 문제를 해결할 수 있다.

 

올바른 풀이는 잘못된 풀이와 동일하게 이중 for문을 통해 소수를 판별하는 것은 동일하지만, 그 범위가 다르다. 

2부터 N-1까지의 수를 검사하는 것이 아니라 N의 제곱근까지만 검사하면 소수를 판단할 수 있다. 

이를 통해 시간복잡도를 잘못된 풀이: O(n)에서 올바른 풀이: O(루트n)만큼으로 떨어트릴 수 있다.

 

문제에 대한 답을 출력할 때도 list의 길이만큼 for문을 돌면서 출력하는 것이 아니라,

포인터를 통해 다음과 같이 한 줄로 출력할 수 있다. 

 

시간 복잡도에 대한 설명은 아래 사진을 보고 이해하실 수 있습니다.

출처 주소도 작성하였기 때문에 더 자세한 풀이가 필요하신 분은 해당 블로그를 참고하시기 바랍니다. (왕추천)

 

 

출처: https://blog.encrypted.gg/983

 

 

에라토스테네스의 체를 통해 소수 찾기

에라토스테네스의 체는 1차원 배열으로 1부터 N까지 소수의 목록을 구하고 싶다고 할 때, N칸짜리 배열을 만든다.

이 배열은 해당 칸의 수가 소수일 경우 true, 아닐 경우 false의 값을 가진다. 

(step1) 초기값으로는 1만 false로 셋팅하고 나머지 수들은 모두 true를 셋팅한다.

 

(step2) 그 다음으로 커서를 1에서 2로 넘겨, 2부터 N까지에 대해 소수를 찾는 것인데,

2는 남겨두고 2의 배수들을 전부 false로 만든다.

 

(step3) 2에 대한 소수 찾기가 끝난 뒤에는 3만 남겨두고 3의 배수들을 전부 false로 만든다.

(step4) 그 다음으로는 4인데, 4는 2의 배수이기 때문에 step2에서 이미 false로 셋팅되었다.

 

(step5) 4에 대한 소수 찾기가 끝났으니, 5에 대한 소수를 찾아야 한다.

이전 step과 동일하게, 5는 남겨두고 5의 배수들을 false로 만든다. 

 

이렇게 stepN까지 반복하여 작업을 수행하면, 최종적으로 소수의 값만 true를 갖는다.

마치 체로 곡식을 거르는것처럼 합성수를 제거해나가는 알고리즘을 에라토스테네스의 체라고 부른다.