[python_파이썬_pass]백준_4948번_베르트랑 공준_풀이

공부하는허딩크 : https://www.youtube.com/live/KtmItpIeYu4?feature=shared

소수판별에 많은 시간을 소비하고 있다.

 

이번에 확실히 잡아야 겠다.

 

<첫번째 시도 : 맞았습니다._2492ms>

바로 에라토스테네스의체 알고리즘을 활용하고 기준은 리스트를 활용했다.

주의할 점은 문제의 조건에서 n보다 크고, 2n보다 작거나 같은 소수의 개수는 n < 소수 <= 2n이라는 점이다.

import sys

input = sys.stdin.readline

while True:

    num = int(input())

    if num == 0:

        break

   

    graph = [i for i in range(num * 2 + 1)]

    cnt  = 0

    for i in range(2, int(2*num**0.5) + 1):

        if graph[i] != 0:

            for j in range(2*i, 2*num + 1, i):

                graph[j] = 0

               

    for i in range(max(2, num+1), 2*num + 1):

        if graph[i]:

            cnt += 1

    print(cnt)

 

<다른사람 풀이 참고>

나랑 비슷하게 풀긴 했는데 참고해보자.

시간적으로 엄청 빠르게 나온다. 136ms

import sys

input = sys.stdin.readline

def Prime():

    for i in range(2, 123456*2 + 1):

        if graph[i]:

            for j in range(i*2, 123456*2 + 1, i):

                graph[j] = 0

       

graph = [1] * (123456*2 + 1)

graph[:2] = [0, 0]

Prime()

while True:

    num = int(input())

    if num == 0:

        break

    print(sum(graph[num+1:2*num + 1]))