約数が1000個ある最小の数は？

どこかの酔っぱらいに問題を出されたので、解いてみた。

「約数が1000個ある最小の自然数はいくつか？但し答えはintの範囲におさまる。」

答えは、810810000。あってますかね？

ある自然数nの約数の数は、nの素因数p1, p2, ..., pmを用いて

n = p1^(k1+1) * p2^(k2+1) * p3^(k3+1) *....., pm^(km+1)

と書けるので、これを使ってメモ化再帰した。

view plainprint?

1. const double inf = (1e+300);  
2. double dp[1024][1024];  
3. bool isPrime[1<<20];  
4. vector<int>primes;  
5. vector<int>facs;  
6.   
7. void init() {  
8.     REP(i, 1<<20) isPrime[i] = true;  
9.     isPrime[0] = isPrime[1] = false;  
10.   
11.     for (int i = 2; i * i <= (1<<20); i++) {  
12.         if (!isPrime[i])  
13.             continue;  
14.         for (int j = i*i; j < (1<<20); j += i)  
15.             isPrime[j] = false;  
16.     }  
17.     primes.clear();  
18.     REP(i, 1<<20) if (isPrime[i]) {  
19.         if (primes.size() > 1024)  
20.             break;  
21.         primes.push_back(i);  
22.     }  
23. }  
24.   
25. double rec(int pw, int pr) {  
26.     if (pw == 1)  
27.         return 1;  
28.   
29.     if (dp[pw][pr] > 0)  
30.         return dp[pw][pr];  
31.   
32.     double ret = inf;  
33.     REP(i, facs.size()) {  
34.         if (pw % facs[i] == 0)  
35.             ret = min(ret, pow(primes[pr], facs[i]-1) * rec(pw/facs[i], pr+1));  
36.     }  
37.   
38.     return dp[pw][pr] = ret;  
39. }  
40.   
41. int main() {  
42.     int n;  
43.     cin >> n;  
44.   
45.     init();  
46.     FOR (i, 2, 1001) {  
47.         if (n % i == 0)  
48.             facs.push_back(i);  
49.     }  
50.   
51.     REP(i, 1024)REP(j, 1024) dp[i][j] = -1;  
52.     cout << (int)rec(n, 0) << endl;  
53. }  

const double inf = (1e+300);
double dp[1024][1024];
bool isPrime[1<<20];
vector<int>primes;
vector<int>facs;

void init() {
    REP(i, 1<<20) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= (1<<20); i++) {
        if (!isPrime[i])
            continue;
        for (int j = i*i; j < (1<<20); j += i)
            isPrime[j] = false;
    }
    primes.clear();
    REP(i, 1<<20) if (isPrime[i]) {
        if (primes.size() > 1024)
            break;
        primes.push_back(i);
    }
}

double rec(int pw, int pr) {
    if (pw == 1)
        return 1;

    if (dp[pw][pr] > 0)
        return dp[pw][pr];

    double ret = inf;
    REP(i, facs.size()) {
        if (pw % facs[i] == 0)
            ret = min(ret, pow(primes[pr], facs[i]-1) * rec(pw/facs[i], pr+1));
    }

    return dp[pw][pr] = ret;
}

int main() {
    int n;
    cin >> n;

    init();
    FOR (i, 2, 1001) {
        if (n % i == 0)
            facs.push_back(i);
    }

    REP(i, 1024)REP(j, 1024) dp[i][j] = -1;
    cout << (int)rec(n, 0) << endl;
}

この結果は面白くて、約数の個数が素数の場合は、その数は合成数個の約数を持つ数と比べて大きな数になることを意味している。

例えば、11個の約数を持つ数。

11はこれ以上因数分解できないため、11個の約数を持つ最小の自然数は上の約数の個数の式より、

2^(10) = 1024となる。

これに対して、12 = 3 * 2 * 2と因数分解できるので、12個の約数を持つ最小の自然数は、

2^2 * 3^1 * 5^1 = 60

となる。

約数の数が1000個である最小の自然数と、約数の数が101個である最小の自然数はどちらが大きいでしょうか？

という問いを考えると、約数の個数が多い1000個の方が大きく思える。しかし実際は、

1000個の場合は、810810000。（答えがあってれば。）

101個の場合は、2^100 ≓　10^30

と101個の方がケタ違いに大きな数となる。