[백준] 4948번 : 베르트랑 공준 - python

링크 : https://www.acmicpc.net/problem/4948

 

---

• 문제

---

• 설계하기(접근방법) 

1. while문을 통해  n을 입력받는다

-> 0이 입력될 때까지 반복되기 때문이다

2. 1부터 루트 n까지의 소수를 리스트로 구한다

3. 2번의 리스트로 아리토스테네스의 체를 적용하여 n 부터 2n까지 소수인지 아닌지 검사한다.

 

결과 : 시간초과

이유 : 케이스마다 아리토스테네스의 체를 거친 소수를 구하는 것은 시간낭비이다

해결방법 -> 리스트를 미리 만들어놓자

 

1. 먼저 1 ~ 246912(123456 * 2)의 루트까지 소수를 구한다.

2. 1번의 리스트로 1 ~ 246912까지 체로 걸러 그 중 소수만 리스트에 적용한다

3. while문을 선언하고, 테스트 케이스마다 fianl_primenum을 순회하며 n < i <= 2n 범위 내에 있다면 count++를 해준다

4. 순회 후 나온 소수의 개수를 출력한다

5. 마지막에 input()을 받아 0이라면 종료, 아니라면 반복한다

 

---

• 코드(출력)

def find_primenumber(num): # 소수를 판별하는 메서드
    if (num == 1):
        return 0
    for i in range(2, num):
        if (num % i == 0):
            return 0
    return num


def find_primenumber2(num, list): # 아르토스테네스의 체
    if (num == 1):
        return 0
    for i in list:
        if (num % i == 0):
            if (num == i):
                return num
            else:
                return 0
    return num


primenum_list = [] # 루트n까지의 소수 리스트

for i in range(1, int(246912 ** (1/2)) + 1):
    if (find_primenumber(i) > 0):
        primenum_list.append(i)

fianl_primenum_list = []
for i in range(1, 246912): # 아리토스테네스의 체
    if (find_primenumber2(i, primenum_list) > 0):
        fianl_primenum_list.append(i) # 체로 걸러진 1~ 246912까지의 소수

n = int(input())

while (n):
    cnt = 0
    for i in fianl_primenum_list:
        if n < i <= 2*n: # 범위 내에 있으면 카운트 + 1
            cnt += 1

    print(cnt)
    n = int(input())

---

• 얻어갈 부분

1. 테스트의 범위가 큰 경우, 그 범위에 해당하는 리스트를 미리 만들어 놓으면 메모리낭비, 시간초과를 방지할 수 있다.빅오를 생각해서 반복문 내에 큰 리스트를 넣는것이 효율적인지, 아니면 반대일지 고민하고 코딩해보자