백준 1929번: 소수 구하기

문제

문제 바로가기> 백준 1929번: 소수 구하기

풀이

제곱근까지만 나뉘어지는지 테스트해보면 된다.

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

def solution():
    import sys
    input = sys.stdin.readline
    m, n = map(int, input().split())
    for i in range(m, n+1):
        if isPrime(i): print(i)
solution()

코드 개선

하지만 위 코드는 일일이 테스트해보기 때문에 제곱근까지만 테스트하더라도 시간이 오래 걸린다.
따라서 다음과 같이하면, 시간이 훨씬 절약된다.

def solution():
    import sys
    input = sys.stdin.readline
    m, n = map(int, input().split())
    li = [False] + [True] * ((n - 1) // 2)
    for x in range(1, int(n**0.5/2+1)):
        if li[x]:
            li[2 * x * (x + 1)::x * 2 + 1] = [False] * ((((n + 1) // 2) - x * x * 2) // (x * 2 + 1))
    if m <= 2:
        print(2)
    print('\n'.join([f'{x}' for x, val in zip(range(m + (m & 1 == 0), n + 1, 2), li[m // 2:]) if val]))
solution()