[백준] 4948: 베르트랑 공준 - 파이썬[python]

다인·2024년 9월 30일

백준

목록 보기

69/112

시간 초과

import sys, math

def isPrime(num):
    if num == 1:
        return False
    for i in range(2, int(num**(1/2))+1): # math.sqrt(n)
        if num % i == 0:
            return False
    return True

n = int(sys.stdin.readline())
while n != 0:
    cnt = 0
    for i in range(n+1, 2*n+1):
        if isPrime(i):
            cnt += 1
    print(cnt)
    n = int(sys.stdin.readline())

이번 문제는 저번과 다르게 시간 제한이 2초에서 1초로 줄었다.
당연히 시간 초과가 나겠거니 했지만 그냥 입력 받는 대로 소수 개수를 쌩으로 구하는 코드를 써봤는데 역시나 시간 초과가 났다.

풀이

전에 시도하려고 했던 대로 소수인 애들을 미리 저장하자고 생각했다.
구글링하면 대부분 리스트에 저장하던데, 이전에 했던 바에 의하면 dictionary와 set이 성능 면에서 좋았기 때문에 얘들로 시도해 보았다.
그런데 생각보다 시간이 걸렸고, 시간을 줄여보는 과정에서 list가 가장 성능이 좋다는 것을 알게 됐다.
이유인 즉슨, 이 문제는 주어진 범위 내의 소수를 찾는 문제이다. 따라서 소수를 저장한 곳에서 범위 내에만 검색을 해보아야 하는데, set과 dictionray는 해시 테이블 기반이라 순서가 없기 때문에 처음부터 끝까지 다 검색해 보아야 한다. 즉, 순차 검색에서는 불리한 것이다.

1. dictionary 이용

import sys

prime = {}
prime[1] = False
for i in range(2, 123456*2+1):
    prime[i] = True
    for j in range(2, int(i**(1/2))+1):
        if i % j == 0:
            prime[i] = False
            break

n = int(sys.stdin.readline())

while n != 0:
    cnt = 0
    for i in range(n+1, 2*n+1):
        if prime[i]:
            cnt += 1
    print(cnt)
    n = int(sys.stdin.readline())

2. set 이용

import sys, math

def isPrime(num):
    for i in range(2, int(num**(1/2))+1): # math.sqrt(n)
        if num % i == 0:
            return False
    return True

prime = set()
for i in range(2, 123456*2+1):
    if isPrime(i):
        prime.add(i)

n = int(sys.stdin.readline())
while n != 0:
    cnt = 0
    for i in range(n+1, 2*n+1):
        if i in prime:
            cnt += 1
    print(cnt)
    n = int(sys.stdin.readline())

isPrime의 인자값으로 2부터 넣도록 코드를 짰기 때문에 isPrime 함수에서 0, 1 등을 검사하는 코드는 넣지 않았다.

3. list 이용

import sys, math

def isPrime(num):
    for i in range(2, int(num**(1/2))+1): # math.sqrt(n)
        if num % i == 0:
            return False
    return True

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

n = int(sys.stdin.readline())
while n != 0:
    cnt = 0
    for i in prime:
        if n < i <= 2*n:
            cnt += 1
    print(cnt)
    n = int(sys.stdin.readline())

3-1. list에서 시간을 더 줄여보자

import sys, math

def isPrime(num):
    for i in range(2, int(num**(1/2))+1): # math.sqrt(n)
        if num % i == 0:
            return False
    return True

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

n = int(sys.stdin.readline())
while n != 0:
    cnt = 0
    for i in prime:
        if 2*n < i:
            break
        if n < i:
            cnt += 1
    print(cnt)
    n = int(sys.stdin.readline())

n < i <= 2n+1로 검사를 하면 모든 prime을 다 검사하기 때문에 2n < i를 먼저 걸러주고 중지해서 시간을 단축시킬 수 있다.

4-1. list를 이용 + 소수 여부를 저장하자(소수인 걸 바꾸기)

import sys, math

def isPrime(num):
    for i in range(2, int(num**(1/2))+1): # math.sqrt(n)
        if num % i == 0:
            return False
    return True

prime = [0]*(123456*2+2) #0부터 123456*2+1까지
for i in range(2, 123456*2+1):
    if isPrime(i):
        prime[i] = 1

n = int(sys.stdin.readline())
while n != 0:
    cnt = 0
    print(sum(prime[n+1:2*n+1]))
    n = int(sys.stdin.readline())

n < i <= 2*n+1 안에 있지 않은 값도 검사하는 게 비효율적이라서 리스트를 슬라이싱해서 소수인 것들만 더하자.
그러기 위해 리스트에 소수인 것들만 넣어놓는 게 아니라, 123456*2+1까지 모든 수를 소수가 아닌지(0) 맞는지(1) 저장한다.

4-2. list를 이용 + 소수 여부를 저장하자(소수가 아닌 걸 바꾸기)

import sys

prime = [0]*2 + [1]*(123456*2+1)  #0부터 123456*2+1까지
for i in range(2, 123456*2+1): # 소수가 아닌 걸 거르기
    if prime[i]:
        for j in range(2*i, 123456*2+1, i):
            prime[j] = 0

n = int(sys.stdin.readline())
while n != 0:
    cnt = 0
    print(sum(prime[n+1:2*n+1]))
    n = int(sys.stdin.readline())

구글링하다 찾은 신박한 방법이다.
소수의 배수는 소수가 아니므로 소수의 배수들을 소거해서 소수만 남기는 방법이다.
이렇게 하면 2부터 √N까지 계속 순회할 필요가 없다. 이전들의 방법은 이미 소수가 아닌 걸 앎에도 저장하지 않았기 때문에 새로운 값이 isPrime에 들어올 때마다 또 소수인지를 검사해서 매우 비효율적이었다. (이걸 왜 몰랐지. 너무 한 방법에만 매몰되었네)
시간이 완전완전 단축되었다.