[til] 알고리즘 백준 1929

📌 오늘의 알고리즘 문제 (소수 구하기)

🚩 문제 설명

백준 1929번: https://www.acmicpc.net/problem/1929

주어진 자연수 M 이상 N 이하의 소수를 모두 출력하는 문제다.

📖 풀이 전략

• 특정 숫자가 소수인지 확인하는 간단한 알고리즘을 사용했다.

• 2부터 그 숫자의 제곱근까지만 나누어보며 나누어떨어지면 소수가 아니다.

• 입력 범위 내 모든 수에 대해 위 과정을 반복했다.

💡 핵심 포인트

• 소수 판별의 효율성

  • 숫자 x가 소수인지 확인할 때 x의 제곱근까지만 확인하면 된다.

  • 이유: 약수가 존재한다면 무조건 제곱근 이하에 존재하기 때문이다.

🛠️ 사용한 알고리즘 및 함수

• 소수 판별 함수 is_prime()

•   def is_prime(x):
        if x == 1:
            return False
        for i in range(2, int(math.sqrt(x) + 1)):
            if x % i == 0:
                return False
        return True
  

📌 배운 점

• 소수를 효율적으로 판별할 때는 제곱근까지만 반복하면 충분하다.

• 범위 내에서 여러 소수를 출력하는 경우, 반복문과 소수 판별 함수를 분리해 가독성을 높일 수 있다.

💻문제풀이 전체코드

import sys
import math


def is_prime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True


m, n = map(int, sys.stdin.readline().split())

for i in range(m, n + 1):
    if is_prime(i):
        print(i)