백준_1929

1929번 소수 구하기

입력하는 두 수를 포함하여 두 수 사이의 소수를 오름차순으로 출력하는 문제.

숫자 범위가 커서 시간 초과를 걱정 했는데 역시나 연속 시간초과가 되었던 문제였다..

# 내가 처음 만들었던 코드

m,n = map(int,input().split())
if m == 1: # 만약 작은 수가 1이면 
    m += 1 # 1은 제외시키기 위해 1을 더해줬다.
for i in range(m,n+1): # 작은수 ~ 큰수 순회
    s = []
    for x in range(2,i+1): 
        if i % x == 0: 
        # 해당하는 숫자까지 나머지가 0인 몫이 있으면 
            s.append(x) # 리스트에 추가
    if len(s) < 2 : # 소수는 리스트에 자기 자신만 있으므로
        print(i) # 리스트의 길이가 2보다 작으면 출력

이중 for 문에 리스트의 조합으로 시간 초과가 되어버렸다.

어떻게든 for 문을 줄여보려고 계속 붙잡고 있었지만
도저히 판단이 안서서 검색해볼 수 밖에 없었다ㅠ

 import sys
 input = sys.stdin.readline

 def prime(i): # 함수 만들기
     if i < 10: # 10보다 작은 수는 그냥 소수를 적어줬다.
         if i in [2,3,5,7]:
             return True
     else:
         for x in range(2,int(i**0.5)+1):
         # 검색결과 입력숫자 까지 확인해 볼 필요없이 입력한 숫자의 
         # 제곱근까지만 확인해 봐도 된다고 한다.
             if i % x == 0: # 나머지가 0인 몫이 있으면 False처리
                 return False
         return True 아니면 True

 m,n = map(int,input().split())

 for i in range(m,n+1):
     if prime(i):
         print(i)

결국 검색해서 통과했다.
이런 방법도 있다는걸 까먹지 않기 위해 다시 쳐보기도 하고
또 다른 방법도 있는지 검색해 봤다.

 n, m = map(int, input().split())
 lst = list(range(m + 1)) # 0~m 까지의 리스트
 for i in lst[2:]: # (0 과 1은 제외)
     if lst[i] >= n: # (n 보다 큰수만 출력)
         print(i)
     lst[i::i] = m//i * [0] 
# i의 배수 자리에 있는 수는 소수가 아니므로 0으로 대입하여 출력하지 않도록 함, 
# 0의 갯수는 제일 큰수를 i로 나눈 몫으로 도출할 수 있다.
# 2부터 시작하므로 2의 배수, 3의 배수, 5의 배수, 7의 배수 순으로 모두 제거할 수 있다.

이런 방법도 있다니 ..!
작은 소수를 출력하고 그 소수의 배수들은 모두 0으로 바꿔
출력하지 않도록 했다.

1개의 for문과 1개의 list로 깔끔하게 정리할 수 있어 좋은 코드인 것 같다. 다양한 방법이 있다는 걸 잊지 말고 한 생각에 붙잡혀 있지 말자!