Algorithm/백준

[백준/Python] 베르트랑 공준

poppy 2021. 10. 1. 16:08
반응형

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

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

import math

while True:
	n = int(input())
	if n == 0:
		break

	prime = [0, 0] + ([1] * (2*n-1)) # 소수 여부 저장 리스트, 0 - 소수X / 1 - 소수O
        # 소수 찾기 - 에라토스테네스의 체
	for i in range(2, int(math.sqrt(2*n+1))+1):
		if prime[i]:
			for j in range(i*2, 2*n+1, i):
				prime[j] = 0

	answer = [i for i in range(n+1, 2*n+1) if prime[i] == 1] # n보다 크고 2n보다 작거나 같은 소수
	print(len(answer))

1. prime 은 소수 여부를 저장하는 리스트이다. 0과 1은 소수가 아니므로 0으로 해주고 나머지는 1로 채워준다.

2. 에라토스테네스의 체를 이용하여 소수를 찾는다.

3. n보다 크고 2n보다 작거나 같은 소수를 뽑아 리스트로 저장한 후 소수의 개수를 출력한다.

반응형

'Algorithm > 백준' 카테고리의 다른 글

[백준/Python] 골드바흐의 추측  (0) 2021.10.03
[백준/Python] 신나는 함수 실행  (0) 2021.10.02
[백준/Python] 피보나치 함수  (0) 2021.09.30
[백준/Python] 스도쿠  (0) 2021.09.21
[백준/Python] N-Queen  (0) 2021.09.20