Baekjoon 문제 풀기 (1929번 : 소수 구하기) Python

1929번 : 소수 구하기

1. 문제읽기

---

에라토스테네스의 체..?

m부터 n까지의 소수를 모두 구하는 문제이다.

2. 제출 코드

---

아니겠지 하면서 시간초과 코드를 열심히 짜보았다.
역시 아니었다.
1부터 n까지의 소수 리스트 중에서 m값을 이진탐색으로 찾아 리스트 슬라이싱을 하는건가? 했는데 완전 잘못 짚었다 ㅋㅋ
그냥 에라토스테네스의 체라는 방식을 이용해서 푸는 문제인 것 같다.

m, n = map(int, input().split())


num = []

for i in range(1, n+1):
	if i == 1:
		continue
	elif i == 2:
		num.append(2)
	elif i >= 3:
		flag = True
		for j in num:
			if i%j == 0:
				flag = False
				break
		if flag:
			num.append(i)

ans = num[num.index(m):]

print(*ans, sep="\n")

3. 공부할 것

---

에라토스테네스의 체

소수를 찾는 방법.
i까지의 소수를 찾을 때 i의 제곱근 까지의 소수들의 배수를 지우고 남는 수를 찾는다.
예를 들면 120까지의 소수를 찾을 때, $11^2$ > 120 이므로 11보다 작은 소수 2, 3, 5, 7의 배수를 지우고 남는 수가 찾는 답이 된다.

아래 정답코드로 채점을 해도 엄청 오래 걸린다..

m, n = map(int, input().split())


def isPrime(num):
    if num == 1:
        return False

    sq = int(num**0.5)  # num의 제곱근 sq

    for i in range(2, sq+1):  # 2부터 sq까지 반복
        if num%i == 0:
            return False
    return True


for i in range(m, n+1):
    if isPrime(i):
        print(i)