[백준] 8단계 - 2581번 (파이썬) check!

 

2581번

https://www.acmicpc.net/problem/2581

 

 

 

 

 💥1929번까지 풀어보고 나니...아래 코드가 매우 비효율적인 코드임을 알게 됨.ㅠㅠ 그냥 기록용 포스팅이라 놔뒀지만...

혹시라도 이 글을 보시는 분들은 아래 코드 참고하지 마세요! 차라리 1929번에 있는 코드나 '소수 구하는 함수' 포스팅에 있는 코드 참고하세요~!!

 

 

## n이하의 자연수 중 소수 찾기 버전1 ##
def prim1(n):
    ans = list(range(2,n+1))
    for i in list(range(2,n+1)):
        for z in list(range(2,i)):
            if (i%z == 0):        
                try:
                    ans.remove(i)
                except:
                    pass              
    return ans

 

 

## n이하의 자연수 중 소수 찾기 버전2 ##
def prim2(n):
    ans = list(range(2,n+1))
    for i in list(range(2,n+1)):
        for z in [x for x in ans if x<i]:
            if (i%z == 0):        
                try:
                    ans.remove(i)
                except:
                    pass                
    return ans

 

 

 

 

두 버전의 차이는 5번째 줄뿐인데, 

prim1 함수를 쓰면 시간초과가 뜨고, 

prim2 함수를 쓰면 정답이 뜸.

 

for z in list(range(2,i))    vs    for z in [x for x in ans if x<i]

그래서 시간복잡도 비교를 해봤는데,

prim1(100) vs prim2(100) 
→ 0.9183000074699521  vs  0.5050000036135316

 

생각보다 많은 차이가 나는 걸 볼 수 있었음.

효율적인 코드를 짜는 게 이렇게 중요한가 봄..💥

 

 

 

 

 

---

 

 

최종 정답코드

def prim2(n):
    ans = list(range(2,n+1))
    for i in list(range(2,n+1)):
        for z in [x for x in ans if x<i]:
            if (i%z == 0):        
                try:
                    ans.remove(i)
                except:
                    pass                
    return ans

M = int(input())
N = int(input())
answer = [i for i in prim2(N) if i>=M]
if len(answer) == 0:
    print(-1)
else:
    print(sum(answer))
    print(min(answer))