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

풀이과정

소수를 구하는 문제이다.
소수는 숫자 1과 자기자신을 약수로 가지는 수로서

쉽게 말해, 2부터 자기자신 - 1 까지 나누어서 나누어떨어지는 숫자가 없으면 소수이다.

첫 번째 코드

위의 설명 그대로를 적용한 코드이지만 시간초과가 나왔다.

if __name__ == "__main__":
    n, m = map(int, input().split())
    ch = [0] * (m+1)
    res = []
    for i in range(n, m+1):
        for j in range(2, i):
            if i % j == 0: 
                break
        else:  # 나누어 떨어지지 않는다면 res 배열에 담기
            res.append(i)

for i in res:
	print(i, end=' ') # 정답 출력

두 번째 코드

에라토스테네스의 체를 이용했다.
에라토스테네스의 체는 소수를 구하는 가장 대표적인 알고리즘이다.

또한 시간 복잡도는 O(Nlog(logN))로서 가장 빠르게 구할수 있다.

방법은 2부터 시작해서 주어진 숫자까지 소수를 찾아낸다.
해당되는 숫자의 곱은 어떤 수의 약수가 되므로 전부 체크해줌으로써 소수를 간단하게 구할 수 있다.

if __name__ == "__main__":
    n, m = map(int, input().split())
    ch = [0] * (m+1)
    res = []
    for i in range(2, m+1):  # 우선 2부터 큰 숫자인 m까지 모든 소수를 res 배열에 담고
        if ch[i] == 0:
            for j in range(i, m+1, i):
                ch[j] = 1
            res.append(i)
            
for i in res:
    if i >= n:   # 조건에 맞춰 정답 출력
        print(i, end=' ')