[소수] 백준 #1929 소수찾기 - Python

🗂️ 문제

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

 

 

💡 접근법

소수는 1과 자기 자신을 제외한 약수가 존재하지 않아야 한다.

소수를 판별하기 위해서는 2부터 √x까지만 나눠보면 된다. x = a * b라고 했을 때 a와 b 중 하나는 반드시 √x 이하이기 때문이다.

 

예를 들어 x = 36 이라고 할 때

• 약수 쌍: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6), (9, 4), (12, 3), (18, 2), (36, 1)
• 즉, 보면 알 수 있듯이, (4, 9) 이후부터는 대칭적으로 반복된다.

 

😎 내 코드

import sys

def gcd(x):
    if x == 1:
        return False
    elif x == 2 or x == 3:
        return True
    else:
        for i in range(2, int(x**0.5)+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 gcd(i):
        print(i)

 

🧐 배운 점

1. ** → 제곱 연산 기호
2. 소수를 구할 때는 제곱근까지만 구하면 된다. 모두 구하는 것은 비효율적이다.

 

✅ 정답 확인