[Python] 자연수 n 이하의 소수 구하기

자연수 n 이하의 소수를 구하는 문제이다.

 

임의의 자연수 n이 소수인지 아닌지 판별하기 위해서는 아래 조건만 확인하면 된다.

 

n을 n^0.5 이하의 소수로 나누었을 때 떨어지지 않아야 함

 

왜 n보다 작은 소수 전체가 아닌 n^0.5 이하의 소수만 테스트해봐도 되는 것일까?

그 이유는 다음과 같다.

 

만약 n이 n^0.5 초과의 m이라는 수로 나누어 떨어진다면

n = m * p 로 표현될 수 있다.

그렇다면 p는 반드시 n^0.5 미만의 수가 된다.

따라서 n이 소수인지 아닌지 판별할 때 m으로 나눠보기 전에 이미 그보다 작은 p로 나눠봤을 것이고

따라서 소수가 아니라는 판단을 했을 것이기 때문에 m까지 도달할 일이 없다.

 

#!/usr/bin/env python3

def getPrimeList(num):
    primes = []
    if num < 2:
        return primes
    for i in range(2, num+1):
        isPrime = True
        for j in primes:
            if i % j == 0:
                isPrime = False
                break
            elif j > i**0.5:
                break
        if isPrime:
            primes.append(i)
    return primes

# 1000 이하의 소수를 출력해보자
if __name__ == '__main__':
    print(getPrimeList(1000))