백준/1929번 :: 소수 구하기 (Python, 파이썬, 알고리즘)

 

문제

---

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

 

 

입력

---

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1≤M≤N≤1,000,000)

 

 

출력

---

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

 

 

예제

---

예제입력

3 16

 

예제출력

3
5
7
11
13

 

파이썬 코드

---

import math

def isPrime(num):
    if num == 1: return False

    n = int(math.sqrt(num))
    for k in range(2, n+1):
        if num % k == 0: return False
    return True

# main
m, n = map(int, input().split())
for k in range(m, n+1):
    if isPrime(k) : print(k)​

 

소수란 약수를 자기 자신과 1을 가지는 숫자를 말한다. 예를들어, 2, 3, 5, 7 등등...

 

위 문제는 1부터 k까지 다 나눠봐도 되지만, 시간을 줄이기 위해 k의 제곱근까지 확인하면 된다.

참고

2018/05/09 - [Language/JAVA] - JAVA :: n까지 모든 소수 구하기, 간단하지만 알아야 하는 코딩

 

2부터 k의 제곱근까지 확인한다. 만약 나누어떨어진다면 그 숫자는 소수가 아니다. 나누어 떨어진다는 것은 다른 약수를 가진다는 뜻.

 

결과

---

 

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

 

안내. 시간제한이 바꼈다고 하시는분이 계셔서 알려드립니다.

백준에서는 파이썬 언어 특성상 C언어보다 실행속도가 느리기 때문에, 시간제한을 늘리고 있습니다. 물론 파이썬 뿐만 아니라 Java의 경우도 해당됩니다.

 

자세한 내용은 https://www.acmicpc.net/help/language를 확인해주세요.

 

 

즉, 위의 문제는 시간제한이 2*3 + 2 = 8초가 되겠네요 ^^

수정일: 2019-04-07

 

문제 출처

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