[알고리즘] 백준 4948 '베르트랑 공준' 풀이 _ 파이썬

백준 4948 베르트랑 공준
https://www.acmicpc.net/problem/4948
난이도 : 실버 2
유형 : 에라토스테네스의 체

문제

※ 베르트랑 공준 : 자연수 n보다 크고 2n보다 작거나 같은 수 중에 소수가 적어도 하나 존재한다.

자연수 n보다 크고, 2n보다 작거나 같은 수 중에 소수가 몇개 있는지 찾는 문제

풀이

풀이 1 -> 시간초과, pypy3로만 성공

def sosu(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False
    else:
        last = round(num ** 0.5) + 1
        for i in range(3, last, 2):
            if num % i == 0:
                return False
    return True

while True:
    x = int(input())
    if x == 0:
        break
    cnt = 0
    for i in range(x+1, 2*x+1):
        if sosu(i):
            cnt += 1
    print(cnt)

그냥 소수 판별 함수를 만들어서 n부터 2n을 모두 검사하는 식으로 풀었는데 python3으로는 시간초과, pypy3로만 성공했다.

풀이 2

check = [0] * 2 + [1] * 246912

#첫 소수만 1로 남기고
#소수의 배수들은 소수가 아니므로 0으로 초기화
for i in range(2, 246913):
    if check[i]:
        for j in range(i * 2, 246913, i):
            check[j] = 0

while True:
    x = int(input())
    if x == 0:
        break
    print(sum(check[x+1:x*2+1]))

에라토스테네스의 체 풀이로 풀어보았다.
n의 범위가 최대 123,456까지이므로 2n의 범위까지 check 배열을 만들어주고,
인덱스가 소수가 아니면 0, 맞으면 1의 값을 넣어줄 것이다!
처음에는 0, 1을 0 나머지는 1이라고 해둔 뒤 for문을 돌면서 2부터 마지막까지 값이 1인 경우 그 수만 소수라고 하고 그 소수의 배수들은 소수가 아니므로 0으로 초기화 해주는 것을 반복한다. 그러면 마지막에는 소수인 값만 1로 남고 나머지는 다 0이 될 것이다.
문제에서 원하는 n보다 크고 2n보다 작거나 같은 범위 내의 소수를 구하기 위해서는 범위대로 배열을 슬라이스 해준 뒤 합을 구한다.

에라토스테네스의 체 풀이 방식으로 진행하면 python3에서도 224ms 시간으로 빠르게 풀어진다.