반응형
오일러 프로젝트 77번 문제. 10을 소수들의 합으로 나누는 경우의 수는 다음과 같이 다섯가지이다.
- 7+3
- 5+5
- 5+3+2
- 3+3+2+2
- 2+2+2+2+2
소수들의 합으로 나누는 경우의 수가 처음으로 5000을 넘는 수는 무엇인가?
from typing import Set, Dict
from functools import lru_cache
from pprint import pprint
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
@lru_cache()
def summations(n: int) -> Set:
# print(">"*depth + str(n))
# depth += 1
if 1 <= n <= 6:
simple_results: Dict[int, Set] = {
1: set(),
2: {(2,)},
3: {(3,)},
4: {(2, 2)},
5: {(2, 3), (5,)},
6: {(2, 2, 2), (3, 3)},
}
# depth -= 1
return simple_results[n]
r = set()
if n in primes:
r |= {(n,)}
for p in primes:
m = n - p
if m <= 1:
break
_r = summations(m)
# print(">"*depth + str(_r))
_r = {tuple(sorted(list(e) + [p], reverse=True)) for e in _r}
r |= _r
# depth -= 1
return r
def main():
s = summations(10)
print(10, len(s), sorted(s, reverse=True))
s = summations(20)
print(20, len(s), sorted(s, reverse=True))
for n in range(100):
s = summations(n)
if len(s) > 5000:
break
print(n, len(s))
pprint(sorted(s, reverse=True))
if __name__ == "__main__":
main()
728x90
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[EP 047] 소인수분해의 소수의 갯수가 4개 (0) | 2021.12.30 |
---|---|
[EP 078] 동전 나누기 (0) | 2021.11.05 |
[EP019] 윤년 (0) | 2021.03.05 |
[EP 074] f(145) = 1! + 4! + 5! = 145 (0) | 2021.02.09 |
1/1, 1/2, ... 1/999 의 순환소수 표현 (4) | 2020.12.02 |