늒네 기록

프로젝트 오일러 97번은 앞에선 열심히 메르센 소수에 대한 설명을 하고, 그 다음엔 넌-메르센 소수 이야기를 하더니, 마지막에 가서는 '앞에 주어진 수의 마지막 10자리 수를 구하시오'라고 하는, 조금 김빠지는 문제다. 이 문제에서 계산해야 하는 수는 28433×2^7830457+1로, 2^7830457를 어떻게 빠르게 계산해내는지가 관건이다. 해당 숫자는 계속 계산하기엔 큰 숫자가 될 것이고, 어차피 우리에게 필요한 숫자는 마지막 10자리 수이며, 그렇기 때문에 계산을 하다가 11자리수가 넘어가면 마지막 10자리 숫자만 잘라서 계속 계산을 이어나가는 방법을 활용할 것이다. 그런데 그렇다고 해도 2^7830457의 마지막 10자리 수를 빨리 계산해내야 하는 문제가 남는다. 문제에 나이브하게 접근하면 이렇..

프로젝트 오일러 13번 문제는 파이썬으로 푼다고 하면 거저 먹는 문제다. 큰 수 연산 문제는, 특히 난이도가 낮은 문제라면 파이썬에서 특별히 신경 써야 하는 부분이 적어진다. 문제에서는 100개의 50자리수가 주어지고, 이를 다 더한 다음 앞의 10자리 수를 구하라고 한다. 이런 유형의 문제를 쉽게 푸는 환경을 세팅하는 것에 이 포스트의 의의를 두겠다. 가장 간단한 방법은, 먼저 코드 자체에 100개의 숫자로 이루어진 리스트를 두고 합을 구하는 것이다. 코드는 다음과 같다. l = [ 37107287533902102798797998220837590246510135740250, ... 53503534226472524250874054075591789781264330331690 ] print(sum(l)) 이..

프로젝트 오일러 7번 문제는 10001번째 소수를 찾으라는 문제다. 에라토스테네스의 체를 활용하여 나이브하게 접근하는 것을 시도해보도록 하자. 먼저, 1부터 10000사이에 있는 소수의 개수를 찾는 것부터 시작해본다. n = 10001 l = [False for _ in range(n)] p = [] for i in range(2, n): if not l[i]: p.append(i) for j in range(i, n, i): l[j] = True print(len(p)) #1229 해당 코드에서는, 크기 10001짜리(즉, 마지막 인덱스가 10000) 리스트 l에 대해서 전부 False를 할당해두고 i = 2일때부터 시작해서 만일 l[i]가 False이면 리스트 p에 더하고 (즉, p는 소수들이 들어있..

[python] string을 list()하면 어떻게 될까? 글에서 이어서, 문제 링크는 프로젝트 오일러 32번. 39 × 186 = 7254 같이, 곱하는 두 수와 곱한 결과에 1부터 9까지 숫자가 다 들어가는 경우를 찾으면 되는데, 이게 뜻하는 것은 결국 str(i) + str(j) + str(i*j)의 결과에 1부터 9까지 숫자가 모두 포함되어 있다는 것과 같다. 그런데 위에서 string을 list로 바꾸는 것이 쉽게 가능함을 보았으니, 이를 바로 활용하면 sorted(list(str(i)+str(j)+str(i*j))) == list('123456789') 이 조건이 true인 경우를 찾는 문제로 바뀐다. i, j중 작은 숫자가 100 이상일 경우, 3자리수 * 3자리수가 최소 5자리수이므로, ..