[파이썬] 단계별 백준 문제 풀기 - 4948 기본수학2 (베르트랑 공준)

문제링크

4948번: 베르트랑 공준

소수구하기 링크(백준 1929)

 

---

<<소스코드>> 맞은답

import math

#소수를 구하는 함수, 자세한 설명은 1929번 포스팅
def prime(n): 
    if n==1:
        return False
    else:
        for i in range(2,int(math.sqrt(n))+1):
            if n%i == 0:
                return False
        return True

# 2부터 246912 까지 담은 리스트 생성 ( +1 해줌/ 246912까지 확인하려고)
general_list = list(range(2,246912))
prime_list = [] #소수 빈리스트를 만들고 리스트에서 소수이면 prime_list에 추가해줬다.
for p in general_list:
    if prime(p):
        prime_list.append(p)

# n과 2n 사이의 소수를 구하는 과정
while True:
    a = int(input()) # input된 n값
    if a == 0: #a가 0이면 while문 종료
        break
    cnt = 0
    for i in prime_list: #소수리스트에서 a와 2a 사이에 있는 소수만 골라서 카운트해준다.
        if a < i <= 2*a:
            cnt += 1
    print(cnt)

<<틀린답>> 

import math

def prime(n):
    if n==1:
        return False
    else:
        for i in range(2,int(math.sqrt(n))+1):
            if n%i == 0:
                return False
        return True

prime_list = []
for p in range(2,246913):
    if prime(p):
        prime_list.append(p)

while True:
    a = int(input())
    if a == 0:
        break
    cnt = 0
    for i in range(a,(2*a)+1): #비효율코드, i는 a만 돌면 되지만, (2a-a) i가 26만번 돌아야 함
        if i in prime_list:
            cnt += 1
    print(cnt)

<<결과값>> 

1
0
10
4
13
3
100
21
1000
135
10000
1033
100000
8392
0

 

---

 

소수리스트를 구했음에도 시간초과가 났다. 이유가 뭘까 하고 곰곰히 맞은답과 비교했더니 이 부분에서 비효율적으로 for문을 돌리고 있었다... 

prime_list에 2부터 26만까지의 소수를 넣어놓고, i가 prime_list를 한번씩 돌면 약 26만번을 돌게 되는데, 

for문에서 range로 a만큼을 더 반복해야하니 a * 26만이 되어버린다. 

   for i in range(a,(2*a)+1):
        if i in prime_list:
            cnt += 1

맞은답을 보면, i는 prime_list 26만개를 돌면서 그냥 밑에 조건에 들어가는지만 체크하면 된다. 그래서 26만번만 그냥 돌면 된다.ㅜㅜㅜ

왜 이 생각을 못했지? 시간복잡도를 고려하면서 문제를  풀어야겠다.

    for i in prime_list:
        if a < i <= 2*a:
            cnt += 1