[백준] 1929번 소수 구하기 | 파이썬 Python

문제

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

 

입력

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

 

출력

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

 

예제

 

나의 풀이

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

for num in range(M, N+1):
    if num == 1:
        continue

    is_prime = True

    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            is_prime = False
            break
    
    if is_prime:
        print(num)

• 1은 두 번째 for문에서 탐색할 수 없기 때문에 따로 if문을 작성해서 소수로 출력되지 않도록 했다.
• 주어진 수가 소수인지 판별하기 위해 2부터 해당 숫자의 제곱근까지를 탐색한다.
• is_prime을 이용해서 해당 자연수가 소수인 경우에만 출력한다.

 

다른 사람의 풀이

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

for num in range(M, N+1):
    if num == 1:
        continue

    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            break
    
    else:
        print(num)

• is_prime을 사용하지 않고 if-else문을 사용했다.
• 두 번째 for문에서 break가 실행되지 않았을 경우, 즉 소수인 경우 else문에서 해당 소수를 출력한다.

 

위 다른 사람의 풀이 / 아래 나의 풀이

• 실행 속도는 첫 번째 방법이 더 빨랐다.