[알고리즘 문제 풀이][파이썬] 백준 1929번: 소수 찾기

백준 1978 문제 링크: https://www.acmicpc.net/problem/1978

📑 문제 설명

주어진 두 수 사이에 있는 소수를 모두 구하는 프로그램 작성

입력: 두 개의 수
출력: 주어진 두 수 사이에 있는 모든 소수

💡 문제 해결 방법

문젤를 풀기 전에 "에라토스테네스의 체" 설명을 먼저 본 후 코딩을 하는 것을 추천한다.

에라토스테네스의 체는 주어진 수 들을 쭉 나열한 후, 2를 제외한 2의 배수 제거, 3을 제외한 3의 배수 제거 를 반복하면서 소수를 찾는 방법이다.

나는 먼저 0부터 1000000 길이의 list를 생성하고, 소수일 경우 True, 소수가 아닐 경우 False를 입력하고 마지막에 True인 index만 출력할 생각이었다.

처음 코드는
2부터 n(두 수 중에 더 큰 수)까지 반복하면서,
index == 2일 때, 3부터 n까지 2로 나누었을 때 나머지가 0인 index 값만 False로 하려 했으나 [시간초과] 발생.

따라서 나머지연산으로 구하는 것이 틀린 방법은 아니지만 곱셈을 사용하면,
index == 2일 때, 2 (n보다 작은 수) <= n 일 경우, [2 (n보다 작은 수) ] index를 False로 만들어주면 훨씬 단축된 시간으로 소수를 구할 수 있다.

💻 코드

import sys


def find_pn(m, n):
    tf_list = [True for i in range(1000001)]
    tf_list[0] = False
    tf_list[1] = False

    for i in range(2, n):
        j = 2
        while(j * i <= n):
            tf_list[j * i] = False
            j += 1


    for i in range(m, n + 1):
        if (tf_list[i] == True):
            print(i)
    return


if __name__ == '__main__':
    m, n = map(int, sys.stdin.readline().split())
    result = find_pn(m, n)

💟 추가적으로 알게 된 점