4184986261 (4184986261,)
4184986262 (2, 2092493131)
4184986263 (3, 997, 1399193)
4184986264 (2, 2, 2, 523123283)
4184986265 (5, 19, 137, 53, 6067)
4184986266 (2, 3, 3, 43, 167, 32377)
4184986267 (73, 73, 47, 31, 11, 7, 7)

1616801030281 (1616801030281,)
1616801030282 (2, 808400515141)
1616801030283 (3, 3359, 160444679)
1616801030284 (2, 2, 11, 36745477961)
1616801030285 (5, 7, 29, 887, 1795837)
1616801030286 (2, 3, 13, 17, 2791, 436871)
1616801030287 (73, 73, 71, 67, 59, 47, 23)

8653695781 (8653695781,)
8653695782 (2, 4326847891)
8653695783 (3, 277, 10413593)
8653695784 (2, 2, 2, 1081711973)
8653695785 (7, 5, 491, 83, 6067)
8653695786 (2, 3, 3, 443, 193, 5623)
8653695787 (79, 53, 31, 29, 19, 11, 11)

2617382974201 (2617382974201,)
2617382974202 (2, 1308691487101)
2617382974203 (3, 3, 290820330467)
2617382974204 (2, 2, 23, 28449814937)
2617382974205 (5, 17, 547, 2657, 21187)
2617382974206 (2, 3, 7, 13, 11, 435794701)
2617382974207 (97, 89, 83, 53, 41, 41, 41)

29432458777 (29432458777,)
29432458778 (2, 14716229389)
29432458779 (3, 467, 21008179)
29432458780 (2, 2, 5, 1471622939)
29432458781 (11, 11, 103, 113, 20899)
29432458782 (2, 3, 3, 3, 19, 28686607)
29432458783 (101, 71, 53, 37, 23, 13, 7)

726524648041 (726524648041,)
726524648042 (2, 363262324021)
726524648043 (3, 5981, 40490701)
726524648044 (2, 2, 13, 13971627847)
726524648045 (5, 7, 47, 47, 9396943)
726524648046 (2, 3, 3, 3, 3347, 4019767)
726524648047 (101, 73, 73, 73, 41, 41, 11)

58623190321 (58623190321,)
58623190322 (2, 29311595161)
58623190323 (3, 10427, 1874083)
58623190324 (2, 2, 4241, 3455741)
58623190325 (5, 5, 7, 2957, 113287)
58623190326 (2, 3, 3, 23, 569, 248861)
58623190327 (101, 71, 61, 61, 13, 13, 13)

28841635441 (28841635441,)
28841635442 (2, 14420817721)
28841635443 (41, 3, 234484841)
28841635444 (2, 2, 43, 167683927)
28841635445 (5, 7, 7, 179, 657659)
28841635446 (2, 3, 13, 47, 593, 13267)
28841635447 (101, 79, 31, 19, 19, 19, 17)

172815695761 (172815695761,)
172815695762 (2, 86407847881)
172815695763 (3, 7753, 7430057)
172815695764 (2, 2, 71, 608505971)
172815695765 (5, 19, 53, 881, 38959)
172815695766 (2, 3, 3, 7, 7, 195936163)
172815695767 (103, 97, 97, 43, 29, 13, 11)

761211180361 (761211180361,)
761211180362 (2, 380605590181)
761211180363 (3, 533219, 475859)
761211180364 (2, 2, 487, 390765493)
761211180365 (19, 5, 37, 677, 319883)
761211180366 (2, 3, 7, 13, 251, 5554421)
761211180367 (107, 67, 59, 59, 59, 47, 11)

102455185801 (102455185801,)
102455185802 (2, 51227592901)
102455185803 (3, 5711, 5979991)
102455185804 (2, 2, 883, 29007697)
102455185805 (5, 131, 7, 193, 115781)
102455185806 (2, 3, 3, 313, 71, 256129)
102455185807 (107, 89, 83, 59, 13, 13, 13)

191871854401 (191871854401,)
191871854402 (2, 95935927201)
191871854403 (3, 2713, 23574377)
191871854404 (2, 2, 53, 905055917)
191871854405 (5, 11, 11, 7, 45306223)
191871854406 (2, 3, 3, 3, 3, 1184394163)
191871854407 (107, 67, 47, 43, 41, 19, 17)

19896463921 (19896463921,)
19896463922 (2, 9948231961)
19896463923 (3, 7, 947450663)
19896463924 (2, 2, 131, 37970351)
19896463925 (13, 5, 5, 2269, 26981)
19896463926 (2, 3, 3, 173, 113, 56543)
19896463927 (107, 31, 29, 23, 23, 23, 17)

856798252201 (856798252201,)
856798252202 (2, 428399126101)
856798252203 (3, 37, 7718903173)
856798252204 (2, 2, 113761, 1882891)
856798252205 (7, 5, 67, 45281, 8069)
856798252206 (2, 13, 3, 89, 23, 5366191)
856798252207 (107, 73, 71, 61, 43, 31, 19)

1952544314857 (1952544314857,)
1952544314858 (2, 976272157429)
1952544314859 (3, 79, 8238583607)
1952544314860 (2, 2, 5, 97627215743)
1952544314861 (7, 17, 373, 2269, 19387)
1952544314862 (2, 3, 3, 3, 419, 86296487)
1952544314863 (107, 103, 89, 71, 53, 23, 23)

99370569721 (99370569721,)
99370569722 (2, 49685284861)
99370569723 (3, 31771, 1042571)
99370569724 (2, 2, 1279, 19423489)
99370569725 (5, 5, 7, 9283, 61169)
99370569726 (2, 3, 3, 43, 1277, 100537)
99370569727 (109, 101, 79, 47, 17, 13, 11)

343097174821 (343097174821,)
343097174822 (2, 171548587411)
343097174823 (3, 13, 8797363457)
343097174824 (2, 2, 2, 42887146853)
343097174825 (5, 5, 71, 5153, 37511)
343097174826 (2, 3, 3, 7, 42403, 64217)
343097174827 (109, 79, 73, 59, 29, 29, 11)

84551522161 (84551522161,)
84551522162 (2, 42275761081)
84551522163 (3, 347, 81221443)
84551522164 (2, 2, 293, 72142937)
84551522165 (5, 11, 613, 1549, 1619)
84551522166 (2, 3, 3, 3, 19, 82408891)
84551522167 (113, 89, 53, 43, 31, 17, 7)

1068580233001 (1068580233001,)
1068580233002 (2, 534290116501)
1068580233003 (3, 5843, 60960707)
1068580233004 (2, 2, 2221, 120281431)
1068580233005 (5, 17, 19, 12853, 51479)
1068580233006 (2, 3, 11, 13, 37, 33660311)
1068580233007 (113, 103, 101, 71, 59, 31, 7)

64230683953 (64230683953,)
64230683954 (2, 32115341977)
64230683955 (3, 5, 4282045597)
64230683956 (2, 2, 863, 18606803)
64230683957 (11, 31, 197, 1487, 643)
64230683958 (2, 3, 3, 7, 167, 3052499)
64230683959 (127, 73, 47, 29, 23, 17, 13)

2240395900321 (2240395900321,)
2240395900322 (2, 1120197950161)
2240395900323 (3, 7, 106685519063)
2240395900324 (2, 2, 103, 5437854127)
2240395900325 (5, 5, 11, 1439, 5661497)
2240395900326 (2, 3, 3, 3, 3, 13829604323)
2240395900327 (127, 101, 73, 67, 67, 41, 13)

417331349353 (417331349353,)
417331349354 (2, 208665674677)
417331349355 (3, 5, 27822089957)
417331349356 (2, 2, 877, 118965607)
417331349357 (13, 283, 619, 457, 401)
417331349358 (2, 7, 3, 11, 101, 8943709)
417331349359 (127, 71, 59, 53, 41, 19, 19)

5568688532521 (5568688532521,)
5568688532522 (2, 2784344266261)
5568688532523 (3, 61, 30429991981)
5568688532524 (2, 2, 13, 107090164087)
5568688532525 (5, 5, 41, 101, 53790761)
5568688532526 (2, 3, 83, 7, 17, 93967273)
5568688532527 (127, 107, 107, 103, 103, 19, 19)

3497714858881 (3497714858881,)
3497714858882 (2, 1748857429441)
3497714858883 (3, 7, 166557850423)
3497714858884 (2, 2, 10253, 85285157)
3497714858885 (5, 13, 223, 499, 483577)
3497714858886 (2, 3, 23, 1129, 641, 35023)
3497714858887 (127, 101, 97, 59, 53, 31, 29)

384213693361 (384213693361,)
384213693362 (2, 192106846681)
384213693363 (3, 29, 4416249349)
384213693364 (2, 2, 17, 5650201373)
384213693365 (5, 19, 439, 1889, 4877)
384213693366 (2, 3, 3, 229, 3203, 29101)
384213693367 (131, 107, 97, 79, 73, 7, 7)

7570707061 (7570707061,)
7570707062 (2, 3785353531)
7570707063 (3, 593, 4255597)
7570707064 (2, 2, 2, 946338383)
7570707065 (5, 43, 79, 233, 1913)
7570707066 (2, 13, 3, 3, 3, 10784483)
7570707067 (131, 71, 31, 31, 11, 11, 7)

294580501321 (294580501321,)
294580501322 (2, 147290250661)
294580501323 (3, 1481, 66302161)
294580501324 (2, 2, 15683, 4695857)
294580501325 (11, 5, 5, 1009, 1061647)
294580501326 (2, 3, 3, 3, 12821, 425489)
294580501327 (131, 101, 59, 47, 37, 31, 7)

2026095491401 (2026095491401,)
2026095491402 (2, 1013047745701)
2026095491403 (3, 3, 225121721267)
2026095491404 (2, 2, 1667, 303853553)
2026095491405 (5, 41, 67, 991, 148853)
2026095491406 (2, 3, 7, 23, 2417, 867773)
2026095491407 (131, 73, 71, 71, 61, 53, 13)

3902104225561 (3902104225561,)
3902104225562 (2, 1951052112781)
3902104225563 (3, 787, 1652733683)
3902104225564 (2, 2, 8171, 119388821)
3902104225565 (5, 13, 7, 13729, 624667)
3902104225566 (2, 3, 3, 73, 293, 10135283)
3902104225567 (131, 89, 89, 89, 47, 31, 29)

27994344883753 (27994344883753,)
27994344883754 (2, 13997172441877)
27994344883755 (3, 5, 1866289658917)
27994344883756 (2, 2, 5477, 1277813807)
27994344883757 (7, 7, 31, 34183, 539141)
27994344883758 (2, 3, 3, 11, 53, 2667652457)
27994344883759 (131, 113, 107, 103, 97, 61, 29)

10467881693221 (10467881693221,)
10467881693222 (2, 5233940846611)
10467881693223 (3, 3583, 973847027)
10467881693224 (2, 2, 2, 1308485211653)
10467881693225 (5, 5, 11, 67829, 561191)
10467881693226 (2, 59, 3, 3, 21101, 467123)
10467881693227 (137, 127, 127, 113, 113, 53, 7)

1823196354961 (1823196354961,)
1823196354962 (2, 911598177481)
1823196354963 (3, 179, 3395151499)
1823196354964 (2, 2, 31, 14703196411)
1823196354965 (5, 59, 67, 3557, 25933)
1823196354966 (2, 3, 3, 7, 2473, 5851117)
1823196354967 (137, 97, 89, 79, 79, 19, 13)

729193382041 (729193382041,)
729193382042 (2, 364596691021)
729193382043 (3, 7, 34723494383)
729193382044 (2, 2, 557489, 326999)
729193382045 (5, 19, 131, 10139, 5779)
729193382046 (2, 3, 3, 3, 3719, 3630971)
729193382047 (137, 107, 73, 53, 43, 23, 13)

6728876983561 (6728876983561,)
6728876983562 (2, 3364438491781)
6728876983563 (3, 7, 320422713503)
6728876983564 (2, 2, 71849, 23413259)
6728876983565 (5, 11, 47, 82529, 31541)
6728876983566 (2, 3, 3, 3, 206221, 604249)
6728876983567 (137, 131, 109, 107, 61, 31, 17)

7019913432241 (7019913432241,)
7019913432242 (2, 3509956716121)
7019913432243 (3, 22303, 104917327)
7019913432244 (2, 2, 83, 21144317567)
7019913432245 (7, 5, 31, 3191, 2027567)
7019913432246 (2, 13, 3, 11, 73, 112078319)
7019913432247 (137, 131, 113, 89, 89, 23, 19)

2534327977177 (2534327977177,)
2534327977178 (2, 1267163988589)
2534327977179 (3, 1277, 661531709)
2534327977180 (2, 2, 5, 126716398859)
2534327977181 (7, 13, 11, 127, 19935403)
2534327977182 (2, 3, 113, 71, 71, 741509)
2534327977183 (137, 131, 109, 79, 31, 23, 23)

16025688105961 (16025688105961,)
16025688105962 (2, 8012844052981)
16025688105963 (3, 5051, 1057591771)
16025688105964 (2, 2, 461, 8690720231)
16025688105965 (5, 19, 17, 66361, 149531)
16025688105966 (2, 3, 3, 7, 11, 11562545531)
16025688105967 (137, 137, 101, 89, 47, 47, 43)

(2,2,2)
(3,2,2)
(3,3,2)
(3,3,3)
(5,2,2)
(5,3,2)
(5,3,3)
(5,5,2)
(5,5,3)
(5,5,5)
(7,2,2)
...

from lib.primes import getPrimes, factorizeRho, isProbablePrime
from itertools import combinations_with_replacement


def gen_k_primes(k):
    primes = []
    for p in getPrimes():
        primes.append(p)
        for n in combinations_with_replacement(primes, k - 1):
            yield (p,) + n[::-1]


def solve(k):

    stack, n = [], 0

    def check():
        if not isProbablePrime(n - k + 1):
            return False

        stack.clear()
        stack.append((n - k + 1, (n - k + 1,)))
        for i in range(2, k):
            fs = factorizeRho(n - k + i)
            if sum(fs.values()) != i:
                return False

            fs_ = []
            for f, e in fs.items():
                fs_ += [f] * e

            stack.append((n - k + i, tuple(fs_)))

        return True

    for factors in gen_k_primes(k):
        n = 1
        for p in factors:
            n *= p

        if not check():
            continue

        stack.append((n, factors))

        for n, fs in stack:
            print(n, fs)
        print()


if __name__ == "__main__":
    solve(7)