[백준] 1929 소수 구하기 (Python 파이썬)

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

1929번: 소수 구하기

문제 설명

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

---

풀이 과정

소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다.

그래서 소수를 판별하는 가장 간단한 방법은

2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다.

 

하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다.

 

그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데

예를 들어, 16이라는 수가 있을 때

16의 약수는 1, 2, 4, 8, 16이며

약수들의 곱으로 나타내면 (1, 16) (2, 8) (4, 4) (8, 2) (16, 1) 다섯쌍의 곱으로 나타낼 수 있다.

 

이렇게 제곱근 4x4를 기준으로 양 옆으로 대칭을 이루기 때문에 제곱근 까지만 검사를 하면 된다.

 

이를 파이썬으로 나타낸 코드는 다음과 같다.

import math

def isPrime(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, input().split())

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

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !