📢 1929번 문제

백준 문제 링크

🔎 풀이

사용 언어 : python
단순 for을 사용하여 문제를 풀면 시간초과가 발생한다.
에라토스테네의 체 방법을 사용하여 문제를 풀어야 한다.

❗ 에라토스테네의 체

에라토스테네스의 체는 소수를 찾는 방법으로
2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

🔎 코드

# 시간 초과
M, N = map(int, input().split())

for i in range(M, N+1):
    count = 0
    for j in range(2, i+1):
        if i % j == 0:
            count += 1
    if count == 1:
        print(i)

#에스토스테네의 체
M, N = map(int, input().split())

sieve = [True] * (N+1) #인덱스[N]을 얻기 위해서 N+1을 해줌
sieve[1] = False # 1은 소수가 아니므로 false

for i in range(2, N+1):
    if sieve[i]: # 배수는 다 False로 바꿨으니 나머지 True인 것들만 수행
        a = 2 
        while i * a <= N:
            sieve[i * a] = False #배수는 false로 바꾸기
            a += 1

for i in range(M, N+1): 
    if sieve[i] == True: # 남은 것들은 소수
        print(i)