[백준][python] 1929번: 소수 구하기

1929번: 소수 구하기

• 백준(boj) 1929번

문제

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

입력 조건

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.

(1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력 조건

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

첫 번째 시도 .

 m,n = map(int,input().split())
 
 for i in range(m,n+1):
   count=0
   for j in range(1,n+1):
     if i%j == 0:
       count+=1
   if count==2:
     print(i)

»intput

3 16

»output

 3
 5
 7
 11
 13

예상은 했다면 역시나… fail

🌝 Thinking

최악의 상황에는 n = 100만 일 수 있다. 따라서 탐색량이 100만 x 100만… 1조 정도의 연산 횟수가 필요,,,, 당연히 시간초과가 나올 것이다.

그래서 학교 수업 중 소수를 빠르게 찾는 방법에 대해서 배운 적 있었다.

바로! 제곱근을 이용하는 것이다. 그 외에도 여러가지 방법 있었던 걸로 기억하는데

따로 방법론을 모아서 포스팅 해야겠다.

---

두 번째 시도 .

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

for i in range(m,n+1):
  if i==1:
    continue
  for j in range(2,int(i**0.5)+1):
    if i%j == 0:
      break
  else:
    print(i)

»intput

3 16

»output

3
5
7
11
13

success

🌝 Thinking

(오,,뭔가 유치 뽕짝하게 그려졌는걸?)

💡 깨달은 점.

1. 소수 탐색에는 여러가지 방법론들이 있다. 제곱근을 이용한 탐색법 정도는 암기하고 있어야겠다.