백준 01929번 / 1929번 문제 링크
문제 이름 : 소수 구하기
주 언어 : Python
태그 : 수학 / 정수론 / 소수 판정 / 에라토스테네스의 체
solved.ac 등급 : Silver III (2023/02/08 확인)
문제 보기
문제 :
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력 :
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력 :
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
소수 에 관련된 문제입니다.
평범한 소수 판별법으로는 풀기 힘들고, 이 문장 쓰면서 문득 그냥 평범한 소수 판별법 으로 못 푸나? 라는 생각이 들어서 해보니 풀어집니다.
에라토스테네스의 체라는 개념을 이해하지 못할 경우에는 그냥 하나하나 일일이 소수판별을 해주어도 괜찮습니다.
최적화고 뭐고 그냥 2부터 $\sqrt{N}$까지 나눠보는 방식으로도 가능합니다.
만약에 이 경우에 시간초과가 나는 경우는 크게 두가지 경우입니다.
1. 하나하나 소수판별을 해주는 경우에는 리스트에 append 해서 나중에 리스트에서 한번에 출력하고...그런 과정 필요없이 그냥 그때그때 출력해도 괜찮습니다.
2. (타언어 기준) 느린 출력법을 쓰는 경우에는 해당 출력법 때문에 늦어지는 경우가 존재합니다. 100만 이하의 소수가 7만 8천개가 있으니 (= 7만 8천번 출력해야 할 수 있음) 더 빠른 출력 방법을 사용하셔야 합니다.
파이썬에서의 print 함수는 충분히 빠르므로 이 부분은 신경 쓸 필요가 없습니다.
물론 이 문제가 일일이 소수판별을 하는 문제는 아니라고 보여집니다. 수 한두개나 혹은 몇개 정도를 판별할 때는 평범한 소수 판별법 나 밀러-라빈 소수 판별법 등을 사용하고,
이렇게 2부터 100만까지 등의 긴 범위의 소수가 필요할 때는 에라토스테네스의 체 를 통상적으로 사용해줍니다.
따라서, 애초에 그냥 문제의 한계인 100만 까지의 모든 소수 리스트를 미리 만들어두고, A이상 B미만이면 출력해주면 됩니다.
( 에라토스테네스의 체 설명은 여기 적어두었습니다. )
다른 언어에서는 100만까지 리스트를 만들어두고, A <= p <= B 일 때만 p를 출력하도록 만들어주면 됩니다.
이 문제는 solved.ac Class 2 에 수록된 문제입니다.
다른 문제도 같이 풀어보시는걸 추천드립니다.
Class 2 문제 모음