본문 바로가기

프로그래밍/알고리즘

[EP 077] 소수의 합으로 나타내는 경우의 수

반응형

오일러 프로젝트 77번 문제. 10을 소수들의 합으로 나누는 경우의 수는 다음과 같이 다섯가지이다.

  1. 7+3
  2. 5+5
  3. 5+3+2
  4. 3+3+2+2
  5. 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