[백준] 1929번 : 소수 구하기

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

1929번: 소수 구하기

해당 문제는 에라토스테네스의 체와 소수를 제곱근까지 확인하여 구하는 방식으로 시간복잡도를 최적화 할 수 있다.

우선 소수를 구할때에 제곱근까지 구하는 방식을 사용한다. 예를들어 20의 소수를 구할때 2부터 20까지 모든 수를 나누어 보면서 나누어 떨어지는지 나누어 떨어지지 않는지 확인하며 소수인지 아닌지 판별한다. 그러나 이 문제는 모든 수를 확인해야 함으로 O(n)의 시간 복잡도가 든다. 그러나 모든 수를 확인하지 않고 제곱수까지만 확인해도 상관이 없다. 약수의 성질을 이용한다. 20의 약수는 1,2,4,5,10,20

1*20 1쌍, 2*10 1쌍, 4*5 1쌍 이기때문에 20의 제곱근인 4까지만 확인해도 상관이 없다.

 

따라서 약수를 구하는 방법으로는 해당 숫자에서 제곱근까지를 나누어보아 나누어 떨어지면 소수가아니고, 나누어 떨어지지 않는다면 소수이다.

 

이렇게 소수를 구한다음, 에라토스테네스의 체의 알고리즘을 이용하여 소수인경우, 소수의 모든 배수들은 소수가 아니기때문에 소수가 아닌 걸로 모두 초기화 해준다.

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

table = [False] * 1000001 # 소수가 아닌수
table[1] = True # 1은 소수가 아니다.
def isPrime(number):
    n = int(number ** 0.5)
    for i in range(2, n+1): # 제곱수까지 나누어 본다.
        if number % i == 0: # 제곱수까지 나누었을때 나누어 떨어지면 약수가 아니다.
            return False
        
    return True # 나누어 떨어졌으면 약수이다.

primelist = [] # 소수를 담는 리스트
for num in range(M, N+1):
    if isPrime(num) and not table[num]:
        primelist.append(num)
        for i in range(num * 2 , N+1, num):
            table[i] = True

for number in primelist:
    print(number)