😊 백준 1929 : 소수 구하기

1929: 소수 구하기

이전에 못 푼 문제 다시 풀었다..

📌 Try 1

import sys

M, N = map(int, sys.stdin.readline().split())
table = list(range(2, N + 1))

i = 0
while i*i <= N:
    j = 2
    while table[i] * j <= N:
        rem = table[i] * j
        if rem in table:
            table.remove(rem)
        j += 1
    i += 1

for x in table:
    if x >= M:
        print(x)

시간 제한이 2초라서 일반적으로 소수 구하는 방법으론 안 될 거라 생각해서 검색해보니, 에라토스테네스의 체라는 개념이 있었다.

이 개념으로 코드를 작성한 건데, 이게 시간초과라서 당황했다.

📌 Try 2

import sys

def delete(first, step):
    if first + step > len(table) - 1:
        return 0
    table[first + step] = 0
    delete(first + step, step)

# input
M, N = map(int, sys.stdin.readline().split())
table, first = [1] * (N + 1), 2

# process
while first * first <= N:
    delete(first, first)
    first += 1

# output
for i in range(M, N + 1):
    if table[i]:
        print(i)

이번에도 에라토스테네스의 체을 재귀로 구현했다.

하지만 이 코드는 런타임 에러 (RecursionError)가 떴다.

python은 재귀 depth가 3000인데 이걸 넘겨서 위의 오류가 뜬 모양이다.

📌 Try 3

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

for x in range(n, m+1):
	flag = 0
	for i in range(2, x//2+1):
		if x % i == 0:
			flag += 1
			break
	if not flag:
		print(x)

다른 분 블로그 코드를 훑어보니, 일반적인 방법으로 작성한 코드가시간초과 뜨지 않았다.

그래서 일반적인 방법으로 소수를 구해봤는데, 이번에도 시간초과 떴다.

ㅎ ㅏ...

📌 Try 4

import sys

sys.setrecursionlimit(10000000)

def delete(first, step):
    if first + step > len(table) - 1:
        return 0
    table[first + step] = 0
    delete(first + step, step)

# input
M, N = map(int, sys.stdin.readline().split())
table, first = [1] * (N + 1), 2
table[1] = 0

# process
while first * first <= N:
    delete(first, first)
    first += 1

# output
for i in range(M, N + 1):
    if table[i]:
        print(i)

하도 안 풀려서 📌 Try 2의 재귀 코드에 depth limit을 10000000으로 늘렸다. 그랬더니, 맞았습니다!!가 뜨긴 했다.

하지만 개운치 않은 느낌..

🎯 Solution

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

M, N = map(int, input().split())

for i in range(M, N+1):
    if isPrime(i):
        print(i)

다른 분 코드를 가져왔다.
이 코드는 소수를 판별하는 가장 일반적인 방법으로 작성됐다.

아래와 같은 내용을 배울 수 있었다.

if num == 1:
	return False

1부터 판별해야 하는 예외적인 상황일 때를 대비한 코드

int(num**0.5)

어떤 수의 루트를 math 라이브러리 없이도 이런 방법으로 구할 수 있다.

🎁 Reference

• [python 파이썬] 백준 1929번: 소수 구하기
  https://deokkk9.tistory.com/17

• 소수 구하기 (에라토스테네스의 체)
  https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/