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

코드 작성

def pr(n):  #함수정의(소수 검출, 에라토스테네스의 체)
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            return False
    else:
        return True
prime = []
for i in range(1, 246913):
    if pr(i):  #만약 i가 소수이면
        prime.append(i)
while True:
    cnt = 0
    n = int(input())
    if n==0:
        break
    for i in prime:
        if n < i <= 2*n:
            cnt += 1
    print(cnt)

 

코드  풀이

#1. 문제풀이

에라토스테네스의 체를 이용하여 1~123456의 2배에 해당하는 246912까지의 수를 p(prime number)라는 리스트 안에 넣는다. while반복문을 이용하여 p안에 있는 소수(i)가 n부터 2n값 사이에 있는 수를 카운트하여 출력한다.

 

#2. 에라토스테네스의 체

숫자 n에 대한 제급근의 배수를 모두 제거하면 소수가 된다. 예를 들어 17까지의 수 중 제곱근은 4이며, 2,3,4의배수를 제거하면 소수가 된다.