백준_1929_소수 구하기_파이썬

문제 출처

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

내 답안

def solution(a, b):
    number = [True for i in range(b + 1)]

    for i in range(2, int(b ** 0.5) + 1):
        if number[i]:
            for j in range(2 * i, b + 1, i):
                number[j] = False

    for index in range(a, b + 1):
        if number[index] and index != 1:
            print(index)


a, b = map(int, input().strip().split(' '))
solution(a, b)

풀이 정리

에라토스테네스의 체 알고리즘을 사용했다. 항상 소수 관련해서 이알고리즘을 써야하는 것을 알고는 있는데, 이해하고 외워서 풀었었는데, 다시 까먹어가지고 생각하면서 풀어보았다.

풀이를 정리해보겠다.

• 1. 입력한 두 숫자중 에서 뒤에 입력한 큰수만큼의 배열을 만들어준다. 이때 배열의 모든 인덱스에는 True값을 넣어준다.
• 2. 이 배열에서 2부터 시작해서 b의 제곱근까지 탐색범위로 잡아주게되는데
     탐색 범위가 N의 제곱근만큼인 이유는 대칭적으로 짝을 이룬다라는 원리를 이용하기 때문이다.
     예를 들어서, 16이라는 수는 1 ×16, 2 × 8, 4 ×4, 8 × 2, 16 ×1로 표현할 수 있다.
     앞서 말한 것처럼 소수는 1과 자기 자신만을 약수로 가지는 수이므로
     약수가 존재하는지 확인하려면 자기 자신의 제곱근만큼만 확인하면 된다!
• 3. 이렇게 i값을 2부터 시작해서 인덱스를 증가시켜주면서 배수만큼 증가시켜주면서 소수가 아닌 인덱스의를 false로 변경해준다.
• 4. 마지막으로 number[index]안에 값이 true이면서 1이 아닌 index숫자를 출력해준다.