[python] 4948. 베르트랑 공준

• 문제 

---

---

• 잘못된 풀이

import sys

while True:
    n = int(sys.stdin.readline())
    if n == 0: # 0이면 끝
        break

    prime_list = []
    for i in range(n, 2*n): # n~2n까지의 수에서
        check = 0
        for j in range(2, int(i**0.5)+1): # 2 ~ 루트n
            if i%j == 0: # 나누어 떨어지면 소수 아님
                check = 1
                break

        if check == 0:
            prime_list.append(i)
    print(prime_list)
    print(len(prime_list))

 

해당 문제도 주어지는 범위 내에서 소수를 구하는 문제이다.

이전 포스팅에서 소수를 다루었듯이 해당 문제도 동일한 로직으로 해결하면 된다고 생각했는데 '시간초과'로 해결하지 못했다.

 

 

 

• 올바른 풀이

import sys

def check_prime(N):
    prime_ = [True] * (N) # list를 먼저 만들어주고

    for i in range(2, int(N**0.5)+1): # 2부터 제곱근 n까지
        if prime_[i]: # true이면
            for j in range(i*2, N, i): # 각 배수들을 false로 만듦
                prime_[j] = False
    return [i for i in range(2, N) if prime_[i] == True]


while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break

    prime_list = check_prime(2*n+1) # n부터 2n 사이의 있는 소수
    answer_list = [num for num in prime_list if num > n] # n보다 큰 수 뽑기
    print(len(answer_list))

 

이번에는 문제를 함수로 나누어 풀어보았다.

에라토스테네스의 체 풀이방법으로 해결했다.

prime_이라는 list를 먼저 만들어주고, 2부터 제곱근 n까지 각 배수들을 false로 만들어 소수만 prime_list에 저장한다.

prime_list 안에 있는 소수들은 2부터 2n보다 작은 수들로 이루어져있기 때문에,

answer_list에서 n보다 큰 (2n보다 작은) 소수들만 남기는 형태로 문제를 해결한다.