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

문제 바로가기

   문제분석   

# 소수 구하는 방법을 함수로 만들고 이를 이용해 문제에서 주어진 범위에서 소수를 구한다.

# 에라토스테네스의 체를 활용해야한다.

# 2부터 시작해서 배수를 구하고, 특정 수의 배수라는 것은 소수가 아니라는 뜻이므로 그 배수를 소수에서 제외하는 방식이다.

 

 

   문제풀이   

 

# 에라토스테네스의 체 개념을 이용해 소수구하는 함수 만들기
def num(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

all_list = list(range(2, 246912))  
save_list = []  
for i in all_list:
    if num(i):
        save_list.append(i)

num = int(sys.stdin.readline())
while num != 0:  
    count = 0  
    for i in save_list:
        if num < i <= num * 2: 
            count += 1 
    print(count)
    num = int(sys.stdin.readline())

# 소수인 2부터 입력받은 값의 제곱근까지만 약수 여부를 판단하면 된다.

# 문제에서 범위를 1 ≤ n ≤ 123,456 로 제한했으므로, 이 범위의 모든 수를 리스트에 담고 소수를 뽑아 낸다.

• 리스트를 하나 선언해 초기화 하고, 반복문으로 함수를 돌려 소수가 나오면 저장한다.
• 해당범위를 반복문으로 돌려 소수 여부를 파악하고 맞다면 초기화한 리스트에 append시킨다.

# 입력값 n이 들어오면 해당 범위의 개수를 구하는데, 

• 초기화했던 리스트가 소수로 다 담겨져 나왔을테니 이를 이용해 입력값 n에 대한 소수 개수를 뽑아낸다.
• 소수가 나오면 카운트 할 변수를 초기화한다.
• 모든 소수가 나올때까지 반복문을 돌리는데, 위에서 구랬던 리스트에서 하나씩 가져와서 그 소수가 입력받은 값들 사이에 있다면 count를 하나씩 추가한다.

 

 

---

   추가내용   

 

# 제곱근을 구할 수 있는 math 모듈의 sqrt( )함수

math.sqrt(num) == num**0.5

import math

print(math.sqrt(25))	# 5
print(math.sqrt(100))	# 10