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

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

4948번: 베르트랑 공준

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보다 작거나 같은 소수를 뽑아 리스트로 저장한 후 소수의 개수를 출력한다.