[기본 수학2] 베르트랑 공준

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

기존에 만들어 놓은 소수 구하는 함수를 돌렸더니 시간초과가 나서 잠시 당황했다.

 

삽질;;;;;

 

매번 소수를 구하는 방식으로는 테스트케이스 갯수대비 짧은 제한시간(1초)을 통과할 수 없을 것 같아서...

 

테스트케이스에 나올 수 있는 소수의 범위 2*123456 내에 있는 소수를 다 구하고 인덱싱 하는 방식으로 전환했다.

 

import math
from sys import stdin

test_case_list = []

while True:
    test_case_num = int(stdin.readline())
    if test_case_num != 0:
        test_case_list.append(test_case_num)
    else:
        break


def prime(num):
    if num == 1:
        return False

    n = int(math.sqrt(num))
    for k in range(2, n + 1):
        if num % k == 0:
            return False

    return True


prime_arr = []
for i in range(1, 123456 * 2 + 1):
    if prime(i):
        prime_arr.append(1)
    else:
        prime_arr.append(0)

for test_case in test_case_list:

    if test_case == 0:
        break

    test_case_max = test_case * 2
    result = prime_arr[test_case:test_case_max]
    # print(result)
    print(result.count(1))

파이썬이 참 인덱싱은 편한 것 같다.

 

데이터 분석 및 연구 분야에서 파이썬으로 할 수 있는 일이 많기도 하고, 언젠가는 파이썬도 제대로 공부해보고 싶다는 생각이 든다.

 

짜잘짜잘하게 프로토타이핑을 한다거나, 파이썬 예제가 쉽다보니 구글 stt등도 파이썬으로 붙여보기는 하는데 업무적으로 제대로 써보거나 각잡고 해본적이 없다보니 항상 궁금하긴 하다.