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

 

 

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

1929번: 소수 구하기

 

 

 

문제

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

 

입력

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

 

출력

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

 

 

 

 

 

 

 

문제 풀이

 

# 소수 구하기

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True


M, N = map(int, input().split())

for i in range(M, N + 1):
    if isPrime(i):
        print(i)

 

 

 

---

 

 

 

소수인지 아닌지 판별하는 함수를 만든 뒤 함수를 호출하는 방식으로 작성하였다.

 

 

처음에는 이중 for문을 이용하여 소수를 리스트에 넣어 출력해주는 방식으로 풀었는데 시간 초과가 났었다. 이에 대한 해결 방법은 for문을 돌 때 나누어주는 수를 2부터 i까지가 아니라 i의 제곱근까지로 바꿔주는 것이다. 소수를 구하는 것이기 때문에 제곱근보다 큰 수는 의미가 없어지기 때문이다.

 

 

 

 

 

 

 

 

시간 초과났던 코드는 다음과 같다.

 

 

# 소수 구하기

M, N = map(int, input().split())
prime_number = list()

for i in range(M, N + 1):
    cnt = 0
    for j in range(1, i + 1):
        if (i % j == 0):
            cnt += 1

    if cnt == 2:
        prime_number.append(i)

for i in prime_number:
    print(i)