백준 1929 파이썬 - 소수 구하기

1. 문제 링크

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

2. 나는 어떻게 생각했는가? 

m, n = map(int, input().split())
for i in range(m, n + 1):
  count = 0
  for j in range(2, i + 1):
    if i % j == 0:
      count += 1
      if count > 1:
        break
  if count == 1:
    print(i)

- 우선 단순 무식하게 접근해보았다. 

- 역시나 시간초과가 발생했다. 

 

- 그래서 이전에 배웠던 제곱근을 이용한 방법과 메소드를 만드는 방법을 사용하기로 했다. 

 

def check_yaksoo(n):
  if n == 1:
    return False
  else:
    for i in range(2, int(n ** 0.5) + 1):
      if n % i == 0:
        return False
    return True

m, n = map(int, input().split())
for i in range(m, n + 1):
  if check_yaksoo(i):
    print(i)

 

 

---

3. 정답 코드

# n 이하의 체를 구하는 함수
def prime(n):
    #0과1은 소수가아니므로 False, 나머지 2부터 n까지는 n-1개임
	seive = [False, False] + [ True ] * (n-1)
	k = int(n ** 0.5)
	#2~ 루트n + 1까지
	for i in range(2, k+1):
		if seive[i]:
			for j in range(i+i, n+1, i):
				seive[j] = False
	return [ i for i in range(2, n+1) if seive[i] == True]
    
m, n = map(int, input().split())

prime_list = prime(n)

for i in prime_list:
	if i < m:
		continue
	print(i)

- 내가 작성한 방식의 코드보다 더 빠르고 강력한 방법이 있다. 

- 바로 '에라토스테네스의 체'라는 방법이다.

- 자세한 설명은 직접 공부해 보는게 좋을 것 같다. 

- 아래의 링크를 확인하기를 바란다. 

 

https://wikidocs.net/21638

위키독스

 

https://leedakyeong.tistory.com/entry/python-소수-찾기-에라토스테네스의-체

[python] 소수 찾기 - 에라토스테네스의 체