[BOJ1929] 소수 구하기

M이상 N이하 소수를 모두 출력

입력

• 첫째줄에 M N (1<= <=1,000,000)
• M~N 사이 소수가 하나이상 무조건 있음

출력

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

설계

• 처음에는 단순히 소수의 정의인, 약수가 1과 자기자신만 있는 방식으로 함수를 짰음
• 시간 초과 뜸
• 검색해보니 ‘에라토스테네스의 체’ 라는 방식을 씀
• n이 소수일 경우 n의 배수는 더이상 소수가 아니다
• 따라서 2부터 N 까지의 소수를 위 방식으로 확인
• Ex) 2는 소수이므로 4, 6, 8, … 모두 소수가 아닌 것으로 체크
  3은 소수이므로 6, 9, 12, 15, … 모두 소수가 아닌 것으로 체크
• 그리고 c++ 은 endl 보다 \n으로 줄 바꿈해야 시간초과 안 뜸(버퍼초기화 관련)

How I solved(click to github)

---

ref :
BOJ1929