백준 1929 소수 구하기 solution[python, 파이썬] - 풀이, 설명::FBTT

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

1929번: 소수 구하기

문제

입출력

1. 소수의 정의를 생각해보기
2. n의 약수의 범위 생각해보기

 

소수란 1과 자기 자신만을 약수로 가지는 수를 말한다.

 

이 문제의 경우 에라토스테네스의 체의 방법을 응용하여 해결하였다.(시간 초과 때문에)

 

에라토스테네스의 체는 2부터 시작하여 우선 2의 배수를 모두 지운다.

2는 소수로 놔둔다

 

3의 배수를 모두 지운다.

3은 2와 마찬가지로 소수로 놔둔다.

 

4는 2의 배수로 지워지고 다음 수인 5의 배수를 모두 지운다.

이러한 방식으로 마지막에 남아있는 수가 소수가 되는 방법이다.

 

에라토스테네스의 체

 

def get_prime(n):
    if n < 2:
        return []
    n += 1
    save = [1] * (n // 2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if save[i // 2]:
            k = i * i
            save[k // 2::i] = [0] * ((n - k - 1) // (2 * i) + 1)
    return [2] + [(2 * i + 1) for i in range(1, n // 2) if save[i]]
 
n, m = map(int, input().split())
p = get_prime(m)
for i in range(len(p)):     #여기부터
    if p[i] >= n:
        for k in p[i:]:     
            print(k)        #여기까지 소수 출력
        break

소수를 모아놓은 list를 얻기 위해 get_prime(n)이라는 함수를 정의하였습니다.

 

n이 2보다 작으면 소수는 존재하지 않으니 빈 list반환

 

save라는 list는 소수인지 아닌지 저장해 놓는 list입니다.

save에는 2를 제외하면 모든 소수는 홀수이니 짝수는 포함되어 있지 않습니다.

 

n의 가장 큰 약수는 √n 이기 때문에 함수 내에서 3부터 2씩 늘려가며(홀수만 검사) int(n ** 0.5) + 1까지 탐색합니다.

save[k // 2::i] = [0] * ((n - k - 1) // (2 * i) + 1) -> 짝수를 제외한 i의 배수를 0(소수가 아님을 나타냄)으로 바꾸는 과정

((n - k - 1) // (2 * i) + 1) -> 0으로 바뀌는 원소의 개수