[Baekjoon / Python] 1929.소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

풀이

처음 풀이 할때는 1978 소수 찾기와 똑같은 줄 알고 그냥

def sosu(num):
	for i in range(2, num):
		if num % i == 0:
			return False
	return True

a,b = map(int,input().split())

for j in range(a,b+1):
	if sosu(j):
		sosu(j)

이런식으로 함수 만들어서 제출했는 데 역시 시간초과 그놈의 ㅅX 시간초과가 났다. 아 역시 for문이 문제구나 생각하고 sys를 사용해보았는 데 결과는 역시 시간초과 그래서 어쩔수 없이 인터넷을 사용했다.
풀이는 엄청엄청 간단했다. "에레토스테네스의 체"를 이용하면 된다. 이름은 엄청 거창한데 간단하다. num의 제곱근까지 반복해서 나누기를 하면 된다.

무슨 말이냐 3부터 16사이의 소수를 구할때 3이 소수인지 판별하는 sosu라는 함수에서 3을 나누기 할때 루트3까지 나누는 거다.
즉, 루트 3은 1.xxx이므로 3은 나눌때 나머지가 0되는 수가 없어서 소수
루트 4는 2이므로 나머지가 0이되는 수 2가 있기 때문에 합성수
루트 5는 2.xxx이므로 나머지가 0이 되는 수가 없기 때문에 소수
.
.
루트 13은 3.xxx이므로 나머지가 0이되는 수가 없기 때문에 소수
루트 14는 3.xxx이므로 나머지가 0이되는 수 2가 있기 때문에 합성수
.

이게 "에레토스테네스의 체"이다.

그래서 완성한 코드

import math
import sys

input = sys.stdin.readline

def sosu(num):
	if num == 1: return False
		
	c = int(math.sqrt(num))
    # num의 제곱근 값을 만듬 이거 대신에
    # int(num**0.5) 이런식으로 함수 없이도 가능함
	
	for i in range(2, c+1):
		if num % i == 0:
			return False
	return True

a,b = map(int,input().split())

for j in range(a,b+1):
	if sosu(j):
		print(j)

끝!