백준: 소수 구하기

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

1929번: 소수 구하기

 

소수를 구하는 식을 표현하는건 쉽다.

하지만 해당 문제의 N의 최대 범위가 100만 까지 들어올 수 있고 시간제한이 2초이기 때문에

시간 복잡도는 O(n^2)이 넘어가서는 안된다.

 

본인도 처음에 이중 포문을 활용하였지만 

수정을 아무리 하여도 시간초과에 막혔었다.

 

알고보니 에라토스테네스의 체라는 공식을 적용해야 통과할 수 있는 문제였다.

에라토스테네스의 체는 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법을 이용한다.

1. 배열 초기화

2. 2부터 시작하고 특정 수의 배수에 해당하는 수를 모두 지운다 ( 자기 자신, 이미 지워진 수 제외 )

3. 2부터 시작하여 남아 있는 수를 모두 가져온다.

이를 반영한 코드는 아래와 같다.

# 3~16 사이에 소수를 찾아라
que = list(map(int, input().split()))

for x in range(que[0], que[1] + 1):
    if x == 1:
        continue
    for j in range(2, int(x**0.5) + 1):
        if x % j == 0:
            break
        else:
            print(x)