[알고리즘] 백준 파이썬 1929번 소수 구하기 | 쉽게 이해하기 | 자세한 설명

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

✔︎ 백준 Python 1929번 소수 구하기 

 

문제

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

 

입력

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

 

출력

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

 

예제 입력, 예제 출력

 

import sys # 파이썬 입력 시스템

m,n = map(int,sys.stdin.readline().split()) 

for i in range (m, n+1) : 
  if i < 2 : # 소수는 무조건 2이상 이므로, 다시 반복문 돌리러 올라감
    continue
  for j in range(2, int(i** 0.5)+1) : (
    if i%j == 0: # 나누어 떨어진다는 것은 다른 약수를 가진다는 의미이므로 break
      break
  else : # 2 이상인데다가, 나누어 떨어지지 않는다면 여기까지 도달해서 출력
    print(i)

✔︎ 3, 16을 입력 받아서 소수를 구해본다고 하자!

 

✔︎ 파이썬 여러 숫자 입력받기

map(int,sys.stdin.readline().split()) 

-> 입력받는 것이 기본적으로 문자열로 받아지기 때문에, 숫자로 변환하기 위해서 앞에 int를 써주었다.

->  ex) 3 16 enter 쳐주면, m = 3, n = 16으로 받아준다.

 

✔︎ range (3, 17)

-> range의 두 번째 argument는 검사하고 싶은 값에서 무조건 1을 더해줘야한다.

-> 따라서 3부터 16까지 검사 가능.

-> 여기서 for i in range(3, 17) 이라면, 3부터 16까지 i가 쭉 돌아준다.

-> 반복을 할 때마다 i가 3, 4, 5, 6... 이런식으로 하나씩 증가해서 도는 것이다.

 

✔︎ if i < 2:

-> 소수는 2이상이어야 하면서 자신과 1밖에 약수가 없는 수이다. 

-> 따라서 2가 아닐 경우에는 바로 식을 빠져나와서(반복문으로 돌아감) 다음 번째 i를 검사할 수 있게 한다.

-> 여기서 break를 쓸 경우, i가 1이라면 바로 종료되기 때문에 2,3,4... 등을 검사할 수 없어서 틀렸다고 나오게 된다.

 

✔︎ range (2, int(i** 0.5)+1)

-> 1은 소수든 아니든 다 나누어떨어지기 때문에 2부터 검사.

-> 그럼, i가 만약 11이었다면, 11/2, 11/3, 11/4, 11/5, .... 11/11 반복. 나눠지는 지로 약수가 있는지 없는지 판단(있으면 소수가 아님)

-> 그런데 i를 전부다 검사해줄 필요가 있을까?

-> 예를 들자면, 16의 약수는 1 2 4 8 16 / 1*16 2*8 4*4 로 대칭

-> 1, 2, 4 만 검사해줘도 충분한 것이다.

-> 그래서 2부터 i의 제곱근까지만 검사해준다.

 

✔︎ if i%j == 0

-> 만약 나누어 떨어진다면, 다른 약수를 가진다는 의미이므로 탈출시켜준다.

-> 그러면 이제 다시 i 반복문으로 돌아가고(얘는 아까 이미 조건을 통과했으니 당연히 계속 실행)

-> 두 번째 for문은 j = 2 부터(탈출했으므로 처음부터 다시 시작) 다시 조건을 실행해줄 것이다.

 

✔︎ 마지막으로, (3 ~ 16)까지의 숫자 중에 2이상을 충족하면서, 나누어떨어지지 않는 것들을 출력해준다. 

-> 반복문 돌면서 n(16) 까지 조건에 맞는 거 다 출력

-> 3, 5, 7, 11, 13이 출력된다.

 

 

 

 

 

 

 

 

참고자료

제곱근으로 구하기 https://hongku.tistory.com/274

제곱근으로 구하기 https://velog.io/@real_jun9u/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-1929%EB%B2%88-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

제곱근으로 구하기 https://sso-feeling.tistory.com/387