백준 - 2839 (Python) - 베르트랑 공준
베르트랑 공준
임의의 자연수 n에 대해 n < x <= 2n 을 만족하는 소수 x의 갯수를 구하는 문제이다.
인풋의 첫 번째 줄에는 테스트 케이스의 횟수가, 끝 줄에는 0이 입력된다.
여러 개의 테스트 케이스가 주어지다가 0이 나타나면 끝나는 방식.
이 문제는 "에라토스테네스의 체"를 사용하는 것이 좋다는 조언을 들어서, 미리 에라토스테네스의 체 파이썬 응용 --> 이 곳에서 파이썬으로 표현하는 방법에 대해 서술해 놓았다.
N = 123456 * 2 + 1
sieve = [True] * N
for i in range(2, int(N**0.5)+1):
if sieve[i]:
for j in range(2*i, N, i):
sieve[j] = False
def prime_cnt(val):
cnt = 0
for i in range(val + 1, val * 2 + 1):
if sieve[i]:
cnt += 1
print(cnt)
while True:
val = int(input())
if val == 0:
break
prime_cnt(val)
코드를 보면 미리 최대 n(<=123456)의 소수를 모두 구해 놓아 처리 시간을 단축시킬 수 있다.
앞서 사용했던 에라토스테네스의 체를 이용하여 모든 소수를 구하고, n+1 <= x <= 2n 범위의 소수를 세어주면 끝!
Author And Source
이 문제에 관하여(백준 - 2839 (Python) - 베르트랑 공준), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@junyp1/백준-2839-Python-6vz6zaeu저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)