신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

 

문제


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의 제곱근까지 확인하면 된다.

 

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

 

결과


 

 

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

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

 

 

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

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

 

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

 

 

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

수정일: 2019-04-07

 

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기