[백준 1929번] 소수 구하기 (Python) (math.sqrt(x), x**0.5 로 x의 제곱근 구하기)

> Python, 수학, 정수론, 소수, 판정에라토스테네스의 체 

 

 

 

 

문제

 

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

 

 

 

입력

 

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

 

 

 

 

출력

 

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

 

 

 

예제 입력 1

 

3 16

 

 

예제 출력 1

 

3
5
7
11
13

 

 

 

내 코드

import math

if __name__ == "__main__":

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

    for i in range(m,n+1):
        if i == 1:
            continue

        for j in range(2, int(math.sqrt(i))+1):
            if i%j==0:
                break
        else:
            print(i)

 

 

 

Point ! ⭐️ 

• 예를 들어 121의 소수를 구할 때는 121이 2 ~ 11 (121의 제곱근) 까지 나눠지는지를 판단하여 소수인지 아닌지를 판단할 수 있다.
  즉 1 ~ 121까지 모든 수로 나눈 나머지가 아닌 2 ~ 11 까지만 하면 되기 때문에 시간 단축을 할 수 있다.
  
  
• mat.sqrt(x) : x의 제곱근
  x**0.5 으로도 사용 가능 !

 

 

 

 

 

백준 

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

1929번: 소수 구하기

 

 

 

참고

https://dongyeopblog.wordpress.com/2016/02/05/python-%EC%A0%9C%EA%B3%B1%EA%B3%BC-%EB%A3%A8%ED%8A%B8-%EA%B5%AC%ED%95%98%EA%B8%B0/