백준 1929. 소수 구하기

def realsosu(num) :
    if num == 1 :
        return False
    else :
        for i in range(2, int(num ** 0.5) +1):
            if num % i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N+1) :
    if realsosu(i) :
        print(i)

 

백준 1929번 문제는 파이썬으로 풀 경우, 에라토스테네스의 체를 사용해야 시간초과가 발생하지 않는다.

시간초과가 발생한 대부분의 코드의 경우 for문이 여러개 사용된 경우가 많았다.

이렇게 되는 까닭에는 문제에서 입력값 범위가 크기 때문이다.

 

 

에라토스테네스의 체는 소수를 찾는 알고리즘이다.

1. 2부터 N까지 모든 수를 나열

2. 2는 소수니까 따로 빼놓고

3. 2의 배수 지우기

4. 3은 소수니까 따로 빼놓고

5. 3의 배수 지우기

6. 5는 소수니까 따로 빼놓고

7. 5의 배수 지우기

8. 7은 소수니까 따로 빼놓고

9. 7의 배수 지우기

10. 11은 소수니까 따로 빼놓고..... 이렇게 계속 반복!

 

그런데 만약 N이 30이라면, 7의 제곱은 49이므로 7의 배수까지 지우지 않아도 된다.

따라서 입력받은 수의 제곱근까지만 검증하면 된다.

 

 

 

 

참고로 아래와 같이 for문을 많이 작성하면 시간초과라고 뜬다... 이런!

m, n = map(int, input().split())
m_list = [] # 사이 수 담는 리스트
y_list = [] # 사이 수의 약수 개수 담는 리스트

# 사이 수 반복문 돌려서 담기
for i in range (m, n+1) :
  m_list.append(i)

# 약수 개수 함수 정의
def weneed(rn) :
    count = 0
    for i in range (1, rn+1) :
        if rn == i :
            count = count + 1
        elif rn % i == 0 :
            count = count + 1
    return count
                
# 사이 수의 각각 약수 개수 담기
for j in range (m, n+1) :
    y_list.append(weneed(j))
    
# 최종 소수 리스트 출력
for i in range (0, len(m_list)) :
    if y_list[i] == 2 :
        print(m_list[i])