[백준] 1929번 소수 구하기, 실버3, python

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

1929번: 소수 구하기

단순히 소수만 구하면 안되고

입력값이 1000000 이므로

시간복잡도 O(N^2)이면 100억이 되어 시간 초과가 뜨게 된다.

 

이런 경우 에라토스테네스의 체의 원리를 구현하여 푸는 것으로 문제를 해결 하면 좋다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

단순 에라토스테네스의 체를 구현한 코드

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

코드 결과

prime_list(20)
[2, 3, 5, 7, 11, 13, 17, 19]

max(prime_list(1000000))
999983

 

 

시간 초과가 나오는 시간복잡도 O(N^2) 방식 코드: 정답은 제대로 잘 나옴

# BOJ_1929

# 각 주어진 수가 소수인지 판별해주는 함수
# 소수: 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
def judgePrime(num):
    if num == 1:
        return
    # num가 2일수도 있잖아!!!!!!
    elif num == 2:
        print(num)
        return

    for i in range(2, num):
        # 5를 1,2,3,4,5로 나눠서 0으로 한번이라도 떨어지지 않으면
        if num % i != 0: # 나누어 떨어지지 않으면
            if i == num - 1:
                print(num)
                return # 소수 맞음
        elif num % i == 0: # 나누어 떨어지면
            return # 소수 아님

# 입력
m, n = map(int, input().split())
for num in range(m, n + 1):
    # 각 주어진 수가 소수인지 판별한다.
    judgePrime(num)

 

에라토스체로 구현된 문제 풀이 코드

# BOJ_1929

def prime_list(m, n):
    n_include = n + 1
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n_include

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    num = int(n_include ** 0.5)
    sieve[1] = False
    for i in range(2, num + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n_include, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(m, n_include) if sieve[i] == True]

# 입력
m, n = map(int, input().split())
answers = prime_list(m, n)
for answer in answers:
    print(answer)

 

중간에 틀렸던 이유: 1을 소수에 포함 시켰으므로 sieve[1] = False를 넣어주었다.