백준 4948 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

베르트랑 공준이라는 게 뭔지 알아보자.

 

n >= 2에 대하여, 두 자연수 n < a < 2n 사이에는 적어도 한 개 이상의 소수가 존재한다.라는 정수론이다.

 

우리가 풀어낼 문제는 그냥 소수의 개수를 알아내면 되는 문제다.

 

코드부터 보자.

 

코드

import sys as s

array = [1 for i in range(246913)]

array[:2] = 0, 0

for i in range(2, 498):

    if array[i]:

        for j in range(i*i, 246913,i):

            array[j] = 0

while n := int(s.stdin.readline()) :

    count = 0

    for k in range(n+1,2*n+1):

        if array[k]:

            count += 1

    print(count)

에라토스테네스 채를 사용하여, 요구되는 전체 범위의 소수를 미리 구해놓은 후, 입력 값 범위에 따른 소수 여부를 카운팅 해서 출력하는 코드이다.

 

또한, 498의 범위까지 검사하는 이유는, 246912의 제곱근+1 값이다.

 

소수를 판별하기 위해, 어떤 값의 제곱근 +1까지의 나눠지는지 여부만 판단하면 구할 수 있기에 해당 값 까지를 범위로 주었다.

 

요즘 게을러졌다.

 

열심히 해야겠다 생각만 하고, 행동에 옮기지 않는다.

 

간절치 않은가보다.

 

배운 점

1. 에라토스테네스 채를 구현하는 방식에 대해 살짝 까먹었는데, 다시 확실하게 익혔다.