[백준 파이썬] # 1929 소수 구하기 (복습 필요)

Silver II

# 1929 소수 구하기

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

1929번: 소수 구하기

 

풀이

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N+1):
    if isPrime(i):
        print(i)

 

후기

• 에라토스테네스의 체를 사용하고, 메모이제이션을 사용했어도 시간초과 오류가 발생했던 문제다. 도저히 혼자서 해결방안을 찾지 못해 정석적으로 풀어낸 분의 코드를 그대로 옮겨 정리해보았다.

• 함수 정의를 통해서 풀이했을 때 정답 처리를 받을 수 있었다. (심지어 sys를 사용하지 않아도 시간초과 발생 x) 왜 그런지 이유를 잘 적어두고 싶지만.. 비전공자의 한계를 느낀다.. 또륵..

• 아래의 코드는 내가 도전했던 코드다. 물론 시간초과 문제로 오답인 코드지만 다시 복습할 때 두 코드의 차이점을 알 수 있었으면 좋겠다는 바람으로.. 남겨둔다. (능력자 분의 조언이 있었으면..)

 

풀이 코드 (시간초과 오류)

import sys
M, N = map(int, sys.stdin.readline().split())
dp = [False] * N

for i in range(M, N):
    check = True
    for j in range(2, int(i**0.5)+1):
        if i%j == 0:
            check = False
    if check:
        dp[i] = True

for i in range(M, N):
    if dp[i]:
        print(i)

 

---

추가 : 함수로 구현하는 것이 더 빠르다

https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function

Why does Python code run faster in a function?

 

• 함수를 사용하게 되면 지역변수(local)을 사용하게 된다. 반면 함수를 사용하지 않으면 모든 변수는 전역변수(global)로 처리된다.
  
  
• 정확한 원리에 대해서 이해하지 못했으나, 아무래도 전역변수의 무게가 지역변수보다 느린 듯 하다. 가급적 함수를 정의해서 풀이하는 연습을 해야할 듯 하다.