[백준 4948번 ] 베르트랑 공준 (파이썬/python)

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

4948번: 베르트랑 공준

처음에 제곱근만을 이용해 소수판별 하는 알고리즘을 짰다. 2번째 코드로 올리겠음

코드는 맞게 짰는데 시간초과가 난다...

 

소수판별 문제에서 시간초과를 안 나게 하라는건 결국 제곱근도 쓰면서 에라토스테네스의 체를 쓰라는말이랑 똑같다.

 

최대값인 123456 의 2배가 되는 인덱스까지 리스트를 만들고

에라토스테네스의 체를 활용해 소수를 구해주었다.

 

그 후 n값을 입력받을때 n+1 ~ 2n까지 소수가 몇 개 있는지 리스트 슬라이싱을 사용해 갯수를 구해주었다.

 

 

에라토스테네스의 체를 이용한 풀이

import sys
from math import sqrt
 
input = sys.stdin.readline
# 에라토스테네스의 체로 123456까지의 모든 소수를 구하자
arr = [True for _ in range(2 * 123457)]
arr[0], arr[1] = False, False
for i in range(2, int(sqrt(2 * 123456)) + 1):
    if arr[i]:
        j = 2
        while i * j <= 2 * 123456:
            arr[i * j] = False
            j += 1
while 1:
    n = int(input())
    if n == 0:
        break
 
    cnt = arr[n + 1:2 * n + 1].count(True)
    print(cnt)
 

 

 

 

 

제곱근만을 이용해 푼 풀이(시간초과뜸)

import sys
from math import sqrt
 
input = sys.stdin.readline
 
while 1:
    n = int(input())
    if n == 0:
        break
 
    cnt = 0
    for num in range(n + 1, 2 * n + 1):
        result = True
        for i in range(2, int(sqrt(num)) + 1):
            # 만약 나눴을때 나누어떨어져서 소수가 아니라면
            if num % i == 0:
                result = False
                break
        if result:
            cnt += 1
    print(cnt)