파이썬으로 소수 찾기
어떻게 효율을 높일 수 있을까?
프로젝트 오일러(Project Euler)라는 걸 하고 있다. 프로그래밍 연습문제(?) 같은 느낌. 사람이 손으로 풀 수 없는 수학문제를 내주고, 간단한 프로그램을 짜서 풀게 하는 방식이다. 뒤에는 간단할지 아닐지 모른다. 나는 방금 막 7번을 푼 상태니까...ㅋㅋ 자주 커밋하는 습관을 들여보고, 생각해서 코드를 짜는 연습을 해보려고 시작했는데 나름 재밌게 하고 있다.
7번 문제는 '소수 찾기'다. 이게 너무 어려워서 며칠 걸렸다. 하루 종일 한 건 아니고 하루에 한두시간씩 쳐다보고 있었는데 답이 잘 안나왔다. '이거다' 싶어서 코드를 짜서 돌려보면 커서가 한참을 깜빡깜빡했다. 이런 게 뭐 그렇지만 잘못 짜면 무한루프 돌리기 쉽다. ctrl+c를 몇 번 눌렀는지 기억도 안남... 하여간 문제는 10001번째 소수를 찾는거다. 우선 내가 만든 답은 이것. 브런치는 왜 스니펫을 안 넣어주냐...
def is_prime(n):
number = 2
prime_numbers = [2]
ox = []
while len(prime_numbers) < n:
number = number + 1
for i in prime_numbers:
ox.append(number % i)
if 0 in ox:
ox = []
else:
prime_numbers.append(number)
print(prime_numbers[n-1])
is_prime(10001)
대략 이런 원리다.
숫자를 하나씩 더해가면서 지금까지 찾아낸 소수로 나눈다(처음에는 2로 나눔)
나머지를 ox라는 리스트에 넣는다
ox리스트에 0이 있으면 나눠떨어졌다는 뜻이므로 소수 리스트(prime_numbers)에 넣지 않는다.
ox리스트에 0이 없으면 소수이므로 소수 리스트(prime_numbers)에 넣는다
입력한 숫자만큼의 소수를 만들때까지 반복
답은 맞았지만 만족스럽진 않다. 과정이 영 안 좋다. 이건 답을 찾는 게 중요한 게 아니다. 효율의 문제다. 내가 짠 함수는 효율이 너무 떨어진다. 이걸 푸는데 컴퓨터가 계산에만 무려 1분 12초를 썼다. 이걸 실제로 써 먹을 수 있나? 이 문제야 소수만 찾으면 되지만, 실제로 동작할 때는 위의 기능이 여러 단계 중 그저 하나일수도 있다. 단순 계산에 1분이 넘는건 너무 길다. 그래서 문제를 풀고난 뒤 다른 사람들은 어떻게 풀었나 좀 찾아봤다. 찾아보니까 효율 따지면서 문제 생각한 사람이 엄청 많다. 어떤 수가 제곱근인지 확인해서 지운다거나...2, 3, 5,7 등 이미 알고 있는 소수의 배수를 미리 배열에서 지운다거나... 에라토스테네스의 체가 가장 효율적이란다. 아니 이런것도 알아야 하나? 아 별로 어려운 내용은 아니구나. 배수를 지워나가며 소수를 찾는건데, 이게 마치 체를 거르는 것 같아서 그렇게 부른다고 한다. 아무튼 코드는 그냥 돌아가게 짜면 끝나는 건 줄 알았는데, 1분 넘게 계산하는 꼴을 보다보니 효율도 중요하다는 걸 배웠다.
덧 +
포스팅을 작성하다가 나름의 개선방법을 하나 찾았다. 소수로 나누다가 나눠떨어지면 루프를 그만 돌게 만드는거다. 이 방법으로 하니까 11초 정도로 연산 시간이 줄었다. 이것도 영 짧은 건 아닌 것 같은데... 아무튼 코드는 다음과 같다.
def is_prime(n):
number = 2
prime_numbers = [2]
ox = []
while len(prime_numbers) < n:
number = number + 1
for i in prime_numbers:
ox.append(number % i)
if number % i == 0:
break
if 0 in ox:
ox = []
continue
else:
prime_numbers.append(number)
print(prime_numbers[n-1])
is_prime(10001)
