找出1到100之间具有最多约数的数字

Question

如何在1到100的范围内找到具有最多因子的最小数字？我知道一个简单的方法是检查每个数字的除数，从1到100，并跟踪具有最大除数的数字。但是有没有更有效的方法呢？

Answer 1

有一种“更简单的方法”，但它是理论上的，而不是真正的计算机算法。出现了两种不同的情况-一种是如果你说的“大多数因素”就是这样，另一种是如果这些因素必须是唯一的。

在第一种情况下，您只需要认识到，为了最大化因子的数量，每个因子需要尽可能小，即2。因子最多的小于100的数字，因此是2的最大幂减去100，恰好是64。

如果因子必须是唯一的，那么我们只需使用2、3、5等(质数)，直到下一个累积乘积大于100 -在本例中，2*3*5=30是具有最多唯一因子的数字。添加第四个因子将使其为210，因此这是我们所能达到的最高值。

Answer 2

对于较小的边界，使用筛子就足够了。从这个事实

         r                   r
(1)  n = ∏ p_k^e_k => τ(n) = ∏ (e_k + 1)
        k=1                 k=1

很明显，因子的数量可以很容易地从n的素因式分解中确定，并且τ(m*n) = τ(m) * τ(n)如果gcd(m,n) = 1 (即τ是乘法函数)。

因此，如果我们知道τ(n)的任何素因数，以及所有n的τ(m)，我们就可以很便宜地计算1 <= m < n。因此

int sieve[limit+1];
// initialise sieve
for(int i = 0; i <= limit; ++i) {
    sieve[i] = i;
}
// find a prime factor for all numbers > 1
int root = sqrt(limit); // limit is supposed to be not too large, so no fixup needed here
for(int p = 2; p <= root; ++p) {
    if (sieve[p] == p) {
        // this means p is prime, mark multiples
        for(int m = p*p; m <= limit; m += p) {
            sieve[m] = p;
        }
}
// Now sieve[n] is a prime factor of n
int p;
for(int n = 2; n <= limit; ++n) {
    if ((p = sieve[n]) == n) {
        // a prime, two divisors
        sieve[n] = 2;
    } else {
        // count the multiplicity of p in n and find the cofactor of p^multiplicity
        int m = 1, q = n;
        do {
            q /= p;
            ++m;
        }while(q % p == 0);
        sieve[n] = m*sieve[q];
    }
}
// Now sieve[n] contains τ(n), the number of divisors of n, look for the maximum
int max_div = 0, max_num = 0;
for(int n = 1; n <= limit; ++n) {
    if (sieve[n] > max_div) {
        max_div = sieve[n];
        max_num = n;
    }
}

在O(N*log log N)时间中查找最大除数计数不超过N的最小数，具有相对较小的常数因子(可以通过单独处理2并仅标记奇素数的奇数倍来进一步减少)。

这是一个简单的暴力方法，对于小N来说已经足够快了(“小”的解释取决于“足够快”的概念，例如可以是<= 1000或<= 1000000 )。

对于更大的边界，这太慢了，而且占用了太多的内存。对于这些，我们需要做更多的分析。

从(1)中，我们可以推断出，在具有相同素因式分解结构的所有数(意味着不同素数因子的相同数目r，以及相同的指数多集，但可能是不同的顺序)中，所有具有相同数目的因子的数中，最小的是其中

• 素数因子是最小的素数，指数按降序出现(2的指数最大，3的指数次之，...)

因此，通过考虑所有有限序列，我们可以找到具有最多因子<= N的最小数

e_1 >= e_2 >= ... >= e_r > 0

使用该属性

                         r
N/2 < n(e_1, ..., e_r) = ∏ p_k^e_k <= N
                        k=1

并且所寻找的号码是由它们产生的n(e_1, ..., e_r)之一。(如果对于单调非递增有限序列为n(e_i) <= N/2，则将1加到e_1的序列将产生一个具有更多因子的数<= N。)

对于与1/log p_k大致成比例的指数，会产生最大的除数计数。更准确地说，对于固定的r，让

                   r
T(x_1, ..., x_r) = ∏ (x_k+1)
                  k=1

                   r
F(x_1, ..., x_r) = ∏ p_k^x_k
                  k=1

然后，T在设置为{ x : F(x) = N and x_k > 0 for all k }的点上采用其最大值

               r
x_k = (log N + ∑ log p_k)/(r * log p_k) - 1
              k=1

我们只允许整数指数，这使问题变得复杂，但偏离比例太远会产生比我们在比例附近发现的更少的除数。

让我们以N = 100000为例进行说明(它有点太小，无法真正利用比例，但足够小，可以完全手工完成)：

1. r = 1：e_1 = 16，n(16) = 2^16 = 65536有17个divisors.
2. r = 2：设置x_2 = x_1 * log 2 / log 3和N = 2^x_1 * 3^x_2 = 2^(2*x_1)，我们得到x_1 ≈ 8.3, x_2 ≈ 5.24。现在让我们看看接近x_1, x_2的e_1, e_2会发生什么。

2^7 *3^6 = 93312，7+1(2^7 *3^6) =(6+1)*(8+1)= 56 2^8 *3^5 = 62208，τ(2^8 *3^5) = (10+1)*(4+1) = 54 2^10*3^4 = 82944，τ(2^10*3^4) =(τ)*(10+1)= 55

偏离比例越远会迅速减少除数计数，

2^11*3^3 = 55296，11+1(2^11*3^3)=(3+1)*(13+1)= 48 2^13*3^2 = 73728，τ(2^13*3^2) = (15+1)*(1+1) = 42 2^15*3^1 = 98304，τ(2^15*3^1) =(τ)*(15+1)= 32

因此，最接近比例的对不会产生最大的除数计数，但具有较大除数计数的对是最接近的three.

• r = 3：。类似地，我们得到x_1 ≈ 5.5, x_2 ≈ 3.5, x_3 ≈ 2.4

2^4 *3^3*5^3 = 54000，τ(2^4 *3^3*5^3) = 5*4*4 =802^5 *3^4*5^2 = 64800，τ(2^5 *3^4*5^2) = 6*5*3 =902^7 *3^3*5^2 = 86400，τ(2^7 *3^3*5^2) = 8*4*3 = 96 2^8 *3^2*5^2 = 57600，τ(2^8 *3^2*5^2) = 9*3*3 = 81 2^6 *3^5*5^1 = 77760，τ(2^6 *3^5*5^1) = 7*6*2 =842 *3^4*5^1 = 51840，τ(2^7 *3^4*5^1) = 8*5*2 = 80 2^9 *3^3*5^1 = 69120，τ(2^9 *3^3*5^1) = 10*4*2 =802^11*3^2*5^1= 92160，τ( 2^11*3^2*5^1 ) = 12*3*2 = 72 2^12*3^1*5^1 = 61440，τ(2^12*3^1*5^1) = 13*2*2 = 52

同样，对于接近proportionality.

• r = 4：的指数，实现了大的除数计数。对指数的粗略近似是x_1 ≈ 4.15, x_2 ≈ 2.42, x_3 ≈ 1.79, x_4 ≈ 1.48。对于e_4 = 2来说，只有一个选择，

2^3*3^2*5^2*7^2 = 88200，τ(2^3*3^2*5^2*7^2) = 4*3*3*3 =88200

对于e_4 = 1，我们有更多的选择：

2^4*3^3*5^2*7^1 = 75600，τ(2^4*3^3*5^2*7^1) = 5*4*3*2 = 120 2^5*3^2*5^2*7^1 = 50400，τ(2^5*3^2*5^2*7^1) = 6*3*3*2 = 108 2^5*3^4*5^1*7^1 = 90720，τ(2^5*3^4*5^1*7^1) = 6*5*2*2 = 120 2^6*3^3*5^1*7^1 = 60480，τ(2^6*3^3*5^1*7^1) = 7*4*2*2 = 112 ^2 8*3^2*5^1*7^1=806401，τ(2^8*3^2*5^1*7^1) = 9*3*2*2 =1082*3^1*5^1*7^1= 53760，τ( 2^9*3^1*5^1*7^1 ) = 10*2*2*2 = 80

• r = 5：x_1 ≈ 3.3, x_2 ≈ 2.1, x_3 ≈ 1.43, x_4 ≈ 1.18, x_5 ≈ 0.96。由于2*3*5*7*11 = 2310，7和11的指数必须是1，所以我们找到候选

2^2*3^2*5^2*7*11 = 69300，τ(2^2*3^2*5^2*7*11) = 3*3*3*2*2 = 108 2^3*3^3*5^1*7*11 = 83160，τ(2^3*3^3*5^1*7*11) =4*4*2*2= 128 2^4*3^2*5^1*7*11 = 55440，τ(2^4*3^2*5^1*7*11) = 5*3*2*2*2 =120^6*3^1*5^1*7*11= 73920，由于2*3*5*7*11*13 = 30030，τ(2^6*3^1*5^1*7*11) = 7*2*2*2*2 = 112

• r = 6：，这里只有一个候选者。

2^2*3*5*7*11*13 = 60060，τ(60060) = 3*2^5 = 96

这比使用四个或五个素数的最佳候选者产生的除数更小。

因此，我们调查了28个候选者(并且可以跳过其中的几个)，发现具有最多因子的最小数目<= 100000是83160 (98280是具有128个因子的100000以下的另一个数字)。

这是一个程序，它可以找到最小的数字，并且最大的因子不超过给定的限制< 2^64 (没有尝试过捷径，因为它对于64位整数足够快，对于任意精度的整数，在某些时候会变得很有价值)：

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    unsigned long long number;
    unsigned long long divisors;
} small_max;

static const unsigned long long primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
static const unsigned long long primorials[] =
    { 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230,
      200560490130, 7420738134810, 304250263527210, 13082761331670030,
      614889782588491410 };

static const unsigned num_primes = sizeof primorials / sizeof primorials[0];

small_max max_divisors(unsigned long long limit);
small_max best_with(unsigned long long limit, unsigned index, unsigned multiplicity);
void factor(unsigned long long number);

int main(int argc, char *argv[]) {
    unsigned long long limit;
    limit = argc > 1 ? strtoull(argv[1],NULL,0) : 100000;
    small_max best = max_divisors(limit);
    printf("\nSmallest number not exceeding %llu with most divisors:\n",limit);
    printf("%llu with %llu divisors\n", best.number, best.divisors);
    factor(best.number);
    return 0;
}

small_max max_divisors(unsigned long long limit) {
    small_max result;
    if (limit < 3) {
        result.number = limit;
        result.divisors = limit;
        return result;
    }
    unsigned idx = num_primes;
    small_max best = best_with(limit,0,1);
    printf("Largest power of 2: %llu = 2^%llu\n", best.number, best.divisors-1);
    for(idx = 1; idx < num_primes && primorials[idx] <= limit; ++idx) {
        printf("Using primes to %llu:\n", primes[idx]);
        unsigned long long test = limit, remaining = limit;
        unsigned multiplicity = 0;
        do {
            ++multiplicity;
            test /= primorials[idx];
            remaining /= primes[idx];
            result = best_with(remaining, idx-1, multiplicity);
            for(unsigned i = 0; i < multiplicity; ++i) {
                result.number *= primes[idx];
            }
            result.divisors *= multiplicity + 1;
            if (result.divisors > best.divisors) {
                printf("New largest divisor count: %llu for\n  ", result.divisors); 
                factor(result.number);
                best = result;
            } else if (result.divisors == best.divisors && result.number < best.number) {
                printf("Smaller number with %llu divisors:\n  ", result.divisors); 
                factor(result.number);
                best = result;
            }
        }while(test >= primorials[idx]);
    }
    return best;
}

small_max best_with(unsigned long long limit, unsigned index, unsigned multiplicity) {
    small_max result = {1, 1};
    if (index == 0) {
        while(limit > 1) {
            result.number *= 2;
            ++result.divisors;
            limit /= 2;
        }
        return result;
    }
    small_max best = {0,0};
    unsigned long long test = limit, remaining = limit;
    --multiplicity;
    for(unsigned i = 0; i < multiplicity; ++i) {
        test /= primorials[index];
        remaining /= primes[index];
    }
    do {
        ++multiplicity;
        test /= primorials[index];
        remaining /= primes[index];
        result = best_with(remaining, index-1, multiplicity);
        for(unsigned i = 0; i < multiplicity; ++i) {
            result.number *= primes[index];
        }
        result.divisors *= multiplicity + 1;
        if (result.divisors > best.divisors) {
            best = result;
        } else if (result.divisors == best.divisors && result.number < best.number) {
            best = result;
        }
    }while(test >= primorials[index]);
    return best;
}

void factor(unsigned long long number) {
    unsigned long long num = number;
    unsigned idx, mult;
    printf("%llu =", number);
    for(idx = 0; num > 1 && idx < num_primes; ++idx) {
        mult = 0;
        while(num % primes[idx] == 0) {
            num /= primes[idx];
            ++mult;
        }
        printf("%s %llu ^ %u", idx ? " *" : "", primes[idx], mult);
    }
    printf("\n");
}

Answer 3

对于从1到100的每个数字，您可以检查它的所有倍数，并添加除数的数量。根据您检查每个数字的除数的方式，它可能会更有效。下面是一段python代码，它实现了这个想法。复杂度为O(N log N)

count=[0]*101
for i in xrange(1,101):
  for j in xrange(1,100/i+1):
    count[i*j]+=1

print max(zip(count,xrange(101))) 

下面是C++的代码

int i,j,count[101];
for(i=1;i<=100;i++) for(j=1;j<=100/i;j++) count[i*j]++;
int max=-1,pos;
for(i=1;i<=100;i++) if(count[i]>=max){
   max=count[i];
   pos=i;
}
printf("%d has %d divisors\n",pos,max);

这两个版本都保留了具有最大因子的所有数字中的最大数字。在这种情况下，96有12个除数。