[BOJ]1929 - 소수 구하기 (Python)

문제

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

코드 #1 - WRONG❌

def is_prime(x):
    for j in range(2, x):
        if x % j == 0:
            return False
    return True

min, max = map(int, input().split())

for i in range(min, max+1):
    if is_prime(i):
        print(i)

풀이 #1 - WRONG❌

실버2인데 너무 쉽게 풀려서 의심스러웠는데 역시나...

시간초과가 떴다.

왜 그런지 백준에 올라와 있는 질문을 검색해보니 에라토스테네스의 체를 공부하고 풀어보라는 글을 발겼했다.

공부하고 다시 풀어봐야지~ 

 

코드 #2

def is_prime_sieve(n, start):
    sieve = [True] * (n+1)
    sieve[0], sieve[1] = False, False

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i + i, n+1, i):
                sieve[j] = False

    return [i for i in range(start, n+1) if sieve[i] == True]

min, max = map(int,input().split())
for k in sorted(is_prime_sieve(max, min)):
    print(k)

풀이 #2

공부하고, 개념 정리하고 다시 문제를 풀어보았다! 

계속 틀려서 왜 틀렸는지 보니까... 

• 0과 1일 때 생각을 하지 않았다. 
• max가 소수일 때를 생각하지 않았다. 

에라토스테네스의 체를 사용해서 소수를 판별하고 나중에 리스트에 넣어줄 때만 입력받은 값의 범위를 고려했다. 

항상 문제를 푸는 과정에서 구멍이 많이 생기는 것 같다. 

모든 상황을 잘 생각하고 반례를 찾는 연습을 많이 해야겠다! 

 

https://hihellosuah.tistory.com/44

[Algorithm]에라토스테네스의 체 - 소수 판별하기