본문 바로가기

프로그래밍/알고리즘

 (46)
[EP 023] 두 과잉수의 합으로 나타낼 수 없는 모든 수의 합 완전수는 자신보다 작은 약수의 합이 자신과 같은 수이다. 예로는 6, 28 등이 있다. 과잉수는 이 합이 자신보다 큰 것을 말한다. 두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은? 자신을 포함하는 모든 약수의 합, 즉 약수함수가 곱셈적이라는 성질 때문에 재귀함수를 만들거나 캐시리스트를 만드는 방식으로 "쪼개서" 문제를 해결하는 전략을 쓸 수 있다. 아래코드는 s 라는 리스트에 약수함수값을 저장하여 n의 약수함수값을 s[n] 으로 가져올 수 있고, n = p q 일 때에, 가장 작은 소수인수를 만나면, s(n) = s[p] s[q] 라는 성질을 이용하여, 차례대로 s 리스트를 채우는 방식으로 문제를 풀어본 것이다. # PROJECT EULER # PROBLEM 23 def s_f(n): """..
[EP 092] T(n) = n의 각 자리수의 제곱의 합. T(T(T(..(n)...))) = n 이 되는 n은 1과 89 # http://projecteuler.net # Problem 92 # 2 2 2 2 2 # 89 -> 8 + 9 = 145 -> 1 + 4 + 5 = 42 -> 20 -> 16 -> 37 -> 58 -> 89 -> ... -> 89 # 1 -> 1 -> 1 from functools import lru_cache import time from tqdm import tqdm BIGN = 10 ** 7 sol_dict = dict() sol_dict[0] = 0 sol_dict[1] = 1 sol_dict[89] = 89 digit_sq = [i * i for i in range(10)] @lru_cache def arrives_at_89_recur(n: int): if n == 0 or n == 1 o..
[EP 005] least common multiple for a list of numbers #################################################### # http://projecteuler.net # # Problem 5 # # 2520 is the smallest number that can be divided # by each of the numbers from 1 to 10 without any # remainder. # # What is the smallest number that is evenly # divisible by all of the numbers from 1 to 20? #################################################### # Author : DwYoon # Date : 2007 04 12 N = ..
[EP 080] 100까지의 정수의 제곱근의 자리수 합 (과거 2007년에 썼던 포스팅 재활용입니다. 접근제한된 블로그에 잠자고 있어서 꺼내옴.) 문제는 이렇다. : 100까지의 정수의 제곱근 중에 무리수인 것의 십진수 소수표현을 구해서, 그 소수표현에 나오는 100개의 자릿수를 더한 값을 모두 더한 값은? 별 생각없이 그냥 순리대로 짜면 구해진다. 무리수가 아닌 건 빼라는 게 함정이었을지도... (실제로 이 조건을 안 써서 한 서너번 재시도. 도대체 틀릴 구석이 없는데...) # http://projecteuler.net/index.php?section=problems&id=80 def GetRoot(n): ret = 0 nn = n digit_sum = 0 for i in range(100): d = 0 while ret*ret
[파이썬] 이집트분수 >>> def egypt(x): ''' x = (a, b) which represent a/b ''' r = [] while x[1]%x[0]: m = x[1]//x[0] + 1 r.append(m) x = (x[0]*m - x[1], x[1]*m) r.append(x[1]//x[0]) print('+'.join('1/%d'%d for d in r)) return r >>> egypt((4, 5)) 1/2+1/4+1/20 [2, 4, 20] >>> egypt((2, 11)) 1/6+1/66 [6, 66] >>> egypt((761, 1000)) 1/2+1/4+1/91+1/91000 [2, 4, 91, 91000] 분수의 이집트분수 분해를 구하는 코드. 버그 없는지 잘 모르겠는데, 일단 깔끔하게 됨.
[EP 048] ∑ i^i (i=1 ~ 1000) 의 마지막 10자리수 구하기 #!/usr/bin/python ############################################################################ # # Problem 48 # 18 July 2003 # 1 2 3 10 # The series, 1 + 2 + 3 + ... + 10 = 10405071317. # # Find the last ten digits of the series, # 1 2 3 1000 # 1 + 2 + 3 + ... + 1000 . ############################################################################ # Author : DwYoon # Date : 2007 04 12 def pow_mod(b..
[EP 050] 연속된소수의합이 다시 소수 무식한 방법으로 푼다. 루프를 빠져나오는 조건을 잘 줘야 빨리 끝난다. 소수를 구할 때, 나눌 수가 소수후보의 제곱근보다 크다면 빠져나오라는 조건을 빼면 시간이 하염없이 걸리고, 연속된소수의 합이 다시 소수인 모든 수를 구하는 것이 아니고, 그 소수 갯수의 최대값을 구한다는 조건을 for 루프에 잘 적용하면 또 시간을 더 단축할 수 있다. 물론 깔끔함은 훼손되지. /* * http://projecteuler.net/index.php?section=problems&id=50 Problem 50 15 August 2003 The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is t..
[Euler Project 134] 1219는 소수 19로 끝나는 23의 배수 5가 아닌 소수의 배수는 마지막 자리수가 1, ... , 9 까지 모두 나온다.

티스토리툴바