[백준 알고리즘] 4948번 베르트랑 공준, 파이썬(python)

4948, 베르트랑 공준

📁 문제 출처

4948번: 베르트랑 공준

 

💡 생각

• 소수의 판별이니까 123,456 * 2 = 246912까지의 소수를 구해놓고
• while문으로 소수 count 하기

 

🛠 나의 코드

n = 246912
arr = [True for i in range(n + 1)] 

for i in range(2, int(n // 2) + 1): 
    if arr[i] == True: 
        j = 2 
        while i * j <= n:
            arr[i * j] = False
            j += 1

arr[0] = False
arr[1] = False

while True:
    data = int(input())
    if data == 0:
        break
    cnt = 0
    for i in range(data+1, (data * 2)+1):
        if arr[i] == True:
            cnt+= 1
    print(cnt)

 

✔️ 배운 점 및 주의할 점

• 에라토스테네스의 체 구하는 문제를 몇 번 풀면 쉽게 풀 수 있다.
• 이전에 비슷한 문제를 풀 때 while문 돌 때마다 소수 판별하는 식을 세웠는데 시간 초과가 발생했다. 그래서 처음부터 소수를 다 구해놓고 풀면 시간을 줄일 수 있다.