冪乗

  • $2^{31} - 1 = 2,147,483,647 \approx 2.1\times 10^9$
  • $2^{63} - 1 = 9,223,372,036,854,775,807 \approx 9.2 \times 10^{18}$
  • $3^{17} \approx 1.3 \times 10^8$
  • $3^{39} \approx 4.1 \times 10^{18}$

階乗，組合せ

  • $8! = 40,320$
  • $10! \approx 3.6 \times 10^6$
  • $20! \approx 2.4 \times 10^{18}$
$n$ $6$ $10$ $16$ $20$ $30$ $40$
$\binom{n}{n/2}$$20$$252$$12,870$$184,756$$1.5\times 10^{8}$ $1.4\times 10^{11}$

参考: Pythonでの計算方法

約数の個数 (最大値)

$n$ 以下の数の約数の個数の最大値．

$n$$10$ $10^5$ $10^8$ $10^9$ $10^{12}$ $10^{15}$
個数$4$ $128$ $768$ $1344$ $6720$ $26880$

参考: より詳しい表 ，高度合成数

約数の個数 (総計)

$c(n)$ を $n$ の約数の個数としたとき，$C(N) := \sum_{n = 1}^{N} c(n)$ の表を示す． 時間は，これを求めるプログラム の実行時間． 実際に約数を求めて数えているので，たとえば $10^6$ までの約数列挙は100msくらいでできるということがわかる．

        N         C(N)    C(N)/N   時間
        256       1,466     5.7   0.000
      1,024       7,262     7.1   0.000
      4,096      34,720     8.5   0.000
     16,384     161,552     9.9   0.002
     65,536     736,974    11.2   0.008
    262,144   3,311,206    12.6   0.028
  1,048,576  14,698,342    14.0   0.117
  4,194,304  64,607,782    15.4   0.493
 16,777,216 281,689,074    16.8   2.081

1000までの素数表

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

素数の分布

$\pi(x)$: $x$ 以下の素数の数

$x$ $10$$10^2$$10^3$$10^4$$10^5$$10^6$
$\pi(x)$ $4$$25$$168$$1229$$9592$$78498$

$\pi(x) \sim \frac{x}{\log x}$ である．

$x$ $10^6$$10^8$$10^{12}$$10^{16}$
$x / \log x$ $7.2\times10^4$$5.4\times10^6$$3.6\times10^{10}$$2.7\times10^{14}$