[백준] 4948번 : 베르트랑 공준 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

4948번: 베르트랑 공준

 

1. 문제 설명

2. 풀이과정

해당 문제는 지정한 범위에서 소수의 개수를 찾는 문제이다.

매번 소수의 개수를 새로 구할 경우 많은 시간이 소모되어 시간초과가 발생하게 된다.

하여 소수를 구할 최댓값이 정해져 있으므로 최댓값까지 소수를 모두 판단하여 저장한 결과를 활용한다.

시간을 조금 더 단축시키기 위해 소수를 판단할 때는 해당 값의 제곱근까지만 확인한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 입력받을 수 있는 n의 최댓값이 123,456이므로 구할 소수의 최대 범위 값은 2 * 123,456까지이다.
3. 하여 해당 범위까지 리스트의 공간을 만들어준다. li = list(True for i in range(123456 * 2 + 1))
4. 해당 리스트의 크기만큼 반복하며 for i in range(len(li))
5. 해당 리스트의 인덱스 값이 소수인지 판단한다. for j in range(2, int(i ** 0.5) + 1)
6. 만약 소수가 아니면 해당 인덱스 위치 값을 False로 바꿔준다. if (i % j == 0): li[i] = False
7. 소수가 아님이 판별되었으므로 판별을 종료한다. break
8. 원하는 횟수만큼 반복하기 위해 무한 반복문을 사용한다. while (True)
9. 값을 입력받고 n = int(sys.stdin.readline())
10. 만약 입력받은 값이 0이면 종료한다. if (n == 0): break
11. 0이 아니면 n보다 크고 2n보다 작거나 같은 소수의 개수를 출력한다. print(li[n + 1 : 2 * n + 1].count(True))

반응형

3. 소스코드

import sys

li = list(True for i in range(123456 * 2 + 1))
for i in range(len(li)):
    for j in range(2, int(i ** 0.5) + 1):
        if (i % j == 0):
            li[i] = False
            break

while (True):
    n = int(sys.stdin.readline())
    if (n == 0):
        break

    print(li[n + 1 : 2 * n + 1].count(True))