fork download
copy 
  1. #!/usr/bin/python3
  2. # -*- coding: utf-8 -*-
  3. # †
  4. from collections import namedtuple
  5. from heapq import heappush, heappop
  6. Tup = namedtuple('Tup', 'cnt, num')
  7.  
  8. def sieve(N):
  9.     is_prime = [False, False] + [True] * (N-1)
  10.     sq = int(N ** .5)
  11.     for i in range(2, sq+1):
  12.         if is_prime[i]:
  13.             for j in range(i*i, N+1, i):
  14.                 is_prime[j] = False
  15.     return [i for i, p in enumerate(is_prime) if p]
  16.  
  17. primes = sieve(50)
  18. N = len(primes)
  19. LIMIT = 10**18
  20.  
  21. pq = []
  22. cnt = 1
  23. x = 1
  24. # 約数の個数、値そのもの、i番目の素数を、icnt個使う
  25. heappush(pq, (cnt, x, 0, 0))
  26. max_cnt = cnt
  27. resArr = []
  28. while len(pq):
  29.     cnt, x, i, icnt = heappop(pq)
  30.     if max_cnt < cnt:
  31.         resArr.append(Tup(cnt, x))
  32.         max_cnt = cnt
  33.     if x * primes[i] < LIMIT:
  34.         # i 番目を icnt 個から 1 個増やして icnt+1 個にする
  35.         heappush(pq, (cnt*(icnt+2)//(icnt+1), x*primes[i], i, icnt+1))
  36.     if i + 1 < N and x * primes[i+1] < LIMIT:
  37.         # i+1 番目を新たに 1 個使う
  38.         heappush(pq, (cnt*2, x*primes[i+1], i+1, 1))
  39.  
  40. # 値で昇順になるように情報をオミットして出力する。
  41. resArr.sort(key=lambda tup: tup.num)
  42. max_cnt = 0
  43. for cnt, num in resArr:
  44.     if max_cnt < cnt:
  45.         max_cnt = cnt
  46.         # 約数の個数, 値
  47.         print(cnt, num)
  48.  
Success #stdin #stdout 4.67s 27736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 2
3 4
4 6
6 12
8 24
9 36
10 48
12 60
16 120
18 180
20 240
24 360
30 720
32 840
36 1260
40 1680
48 2520
60 5040
64 7560
72 10080
80 15120
84 20160
90 25200
96 27720
100 45360
108 50400
120 55440
128 83160
144 110880
160 166320
168 221760
180 277200
192 332640
200 498960
216 554400
224 665280
240 720720
256 1081080
288 1441440
320 2162160
336 2882880
360 3603600
384 4324320
400 6486480
432 7207200
448 8648640
480 10810800
504 14414400
512 17297280
576 21621600
600 32432400
640 36756720
672 43243200
720 61261200
768 73513440
800 110270160
864 122522400
896 147026880
960 183783600
1008 245044800
1024 294053760
1152 367567200
1200 551350800
1280 698377680
1344 735134400
1440 1102701600
1536 1396755360
1600 2095133040
1680 2205403200
1728 2327925600
1792 2793510720
1920 3491888400
2016 4655851200
2048 5587021440
2304 6983776800
2400 10475665200
2688 13967553600
2880 20951330400
3072 27935107200
3360 41902660800
3456 48886437600
3584 64250746560
3600 73329656400
3840 80313433200
4032 97772875200
4096 128501493120
4320 146659312800
4608 160626866400
4800 240940299600
5040 293318625600
5376 321253732800
5760 481880599200
6144 642507465600
6720 963761198400
6912 1124388064800
7168 1606268664000
7200 1686582097200
7680 1927522396800
8064 2248776129600
8192 3212537328000
8640 3373164194400
9216 4497552259200
10080 6746328388800
10368 8995104518400
10752 9316358251200
11520 13492656777600
12288 18632716502400
12960 26985313555200
13440 27949074753600
13824 32607253879200
14336 46581791256000
14400 48910880818800
15360 55898149507200
16128 65214507758400
16384 93163582512000
17280 97821761637600
18432 130429015516800
20160 195643523275200
20736 260858031033600
21504 288807105787200
23040 391287046550400
24576 577614211574400
25920 782574093100800
26880 866421317361600
27648 1010824870255200
28672 1444035528936000
28800 1516237305382800
30720 1732842634723200
32256 2021649740510400
32768 2888071057872000
34560 3032474610765600
36864 4043299481020800
40320 6064949221531200
41472 8086598962041600
43008 10108248702552000
46080 12129898443062400
48384 18194847664593600
49152 20216497405104000
51840 24259796886124800
53760 30324746107656000
55296 36389695329187200
57600 48519593772249600
61440 60649492215312000
62208 72779390658374400
64512 74801040398884800
65536 106858629141264000
69120 112201560598327200
73728 149602080797769600
80640 224403121196654400
82944 299204161595539200
86016 374005201994424000
92160 448806242393308800
96768 673209363589963200
98304 748010403988848000
103680 897612484786617600
https://ideone.com/yBaLA0
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!