Baekjoon 1929번 소수 구하기

문제

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

걸린 시간

- 실패

시간 초과 풀이

Python3

if __name__ == "__main__":    
    M, N = map(int, input().split())

    flag = True

    for i in range(M, N+1):
        # 만약 소수이면 출력
        # 자신을 제외한 최대 약수는 자신의 절반을 넘지 않는다고 한다.
        for j in range(2, int(i/2)+1):
            print(i, j)
            if i % j == 0:
                flag = False 
                print("break")
                break    
        # 소수이면    
        if flag == True:
            print(i)

        flag = True

소수인지 아닌지를 자신보다 작은 모든 값으로 나누어 떨어지는가를 확인하는 방법에서, 자신을 제외한 최대 약수는 자신의 절반을 넘지 않는다는 점을 이용하여 반복횟수를 조금 줄인 예제.

백만 이하의 소수를 찾아내기엔 너무 느린 알고리즘.

if __name__ == "__main__":    
    M, N = map(int, input().split())

    flag = True

    prime = [2]

    for i in range(2, N+1):
        # 소수를 저장해두고 입력받은 수 보다 작은 소수들로 나누어 본다.
        for j in range(0,len(prime)):
            if i % prime[j] == 0:
                flag = False 
                break    
        # 소수이면    
        if flag == True:
            prime.append(i)

        flag = True

    # M미만의 값들은 출력하지 않는다.
    for i in prime:
        if not i < M:
            print(i)

입력받은 수 보다 작은 수의 소수들로 나누어 소수인지를 확인하는 예제. prime 이란 리스트를 두어 소수를 저장하고 저장된 값들로 입력받은 수를 나눈다.

첫번째 코드보다 수행시간이 훨씬 줄지만 문제를 통과하기엔 여전히 느리다.

옳은 풀이

Python3

if __name__ == "__main__":
    M, N = map(int, input().split())

    arr = [0] * (N+1)

    for i in range(2, N+1):
        arr[i] = i

    for i in range(2, N+1):
        # 이미 체크된 수의 배수는 확인하지 않는다.
        if arr[i] == 0:
            pass
        else:
            # i를 제외한 i의 배수들은 0으로 체크
            j = i + i
            while j < N+1:
                arr[j] = 0
                j += i # i의 배수

    # 출력
    for i in range(2, N+1):
        if arr[i] != 0:
            if not arr[i] < M:
                print(i)

에라토스테네스의 체 라고 하는 알고리즘을 이용하면 기가 막힌 속도로 소수를 찾아낼 수 있다.

간단히 요약하면 자기 자신을 제외한 배수들을 모두 체크해 나간다. 체크되지 않은 수들이 소수이다. 이미 체크된 수들은 소수가 아니므로 확인하지 않고 건너뛰기 때문에 반복되는 횟수가 훨씬 줄어든다.

아래 걸어둔 블로그 링크에서 정말 잘 설명해 주었다.

참고

• [C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체