[BOJ/백준] 1929번 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

---

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

입/출력

---

풀이

a,b = map(int,input().split()) #두개의 값을 띄어쓰기로 구분지어서 입력

def prime(num): #소수 찾는 함수
  if num == 1: #1이면 False
    return False
  elif num ==2: #2부터는 True
    return True 
  for i in range(2,int(num**0.5)+1): #에라토스테네스의 체를 안다면 제곱근을 이용해서 푸는것이 시간 단축에 좋음
    if num%i == 0:
      return False
  return True

for i in range(a,b+1):
  if prime(i):
    print(i)

결과

---

코드 풀이

처음에는 set을 이용해서 풀려고 했다. set은 중복을 최소화해주는 거지 중복을 제거해주는 함수가 아닌데 헷갈려서 헛 짓을 했다.  그리고 다음에는 에라토스테네스의 함수를 그대로 이용해 두개의 배열을 생성해 큰 수의 소수를 담은 배열에서 작은 수의 배열을 처리하는 방식으로 처리했는데 만약 B라는 큰 수에서 나온 소수 배열이 A라는 작은 소수 배열에 있는 값을 가지고 있다면 해당 배열의 인덱스를 remove 하는 방법으로 처리했는데 당연히 시간 초과를 먹었다. 쓸데없는 함수를 이용했기 때문.

 

다시 생각해보니 굳이 이렇게 풀 필요가 없었다. 에라토스테네스의 체에서 이용한 제곱근을 그대로 가져오고 그냥 for문을 통해서 a~b+1까지 돌려주면 끝.. 왜 고민했나 싶다.