[BOJ] 1929.소수구하기 (Python)

 

1929번: 소수 구하기

 

해당 문제는 M 이상 N 이하의 수 중 소수인 경우 출력하는 문제입니다.

소수 문제는 에라토스테네스의 체를 이용하면 쉽게 풀 수 있습니다.

 

# 소수 구하기

M, N = map(int, input().split())
check = [0] * (N + 1) # 소수 확인을 위한 용도

for i in range(2, N + 1) : # 에라토스테네스체의 이용
    if check[i] == 0 :
        if i >= M :
            print(i)
        for j in range(i, N + 1, i) :
            check[j] = 1

---

에라토스테네스의 체는 무엇일까요?

에라토스테네스의 체는 소수를 판별하는 알고리즘입니다.

이 알고리즘은 특정 소수의 배수들을 계산에 포함되지 않도록 하는 원리인데,

이것이 마치 체에 걸러지는 것과 같아 에라토스테네스의 체라고 불립니다.

 

구현하는 방식은 다음과 같습니다.

1. 소수를 판별할 범위만큼 배열을 생성하고 0으로 초기화합니다. (저는 개인적으로 0 초기화를 좋아해요 😄)
2. 2부터 시작해서 배수에 해당하는 숫자들을 지우며 진행합니다.
3. 2부터 시작하여 지워지지 않은 수들은 모두 소수이므로 출력합니다.

에라토스테네스의 체 구현하기

def find_prime_number(N) :
    check = [0] * (N + 1)
    result = []
    for i in range(2, N + 1) :
        if check[i] == 0 :
            for j in range(i*2, N + 1, i) :
                if check[j] == 0 :
                    check[j] = 1

    for i in range(2, N + 1) :
        if check[i] == 0 : result.append(i)
    return result

if __name__=="__main__" :
    N = 100
    print(find_prime_number(N))