查找範圍在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

對於從1到100的每個數字，您可以檢查它的所有倍數並添加除數。根據你如何檢查每個數字的除數，它可以更高效。這是一個可以實現這個想法的python代碼。複雜度爲O（N日誌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個除數。

Answer 3

你可以從Eratosthenes算法的篩選中獲得一些想法。唯一的事情是你需要從2 * i而不是i * i運行內部循環。但這種算法比爲O（n^2）快

int a[]=new int[101],max=0,index=-1; 
for(i=2;i<=100;i++) 
{ 
if(a[i]==0) 
for(j=2*i;j<=100;j+=i) 
a[j]++; 
if(a[i]>max) 
{ 
index=i; 
max=a[i]; 
} 

這給你30除數號爲3，如果你想在回答變種

Answer 4

人會的方式，您可以修改內部循環是避免奇數..

int mostDivisors(int min,int max) 
{ 
    int i,j,pc=0,cc=0,no=0; 
    min=(min%2==0)?min:min+1;//making it even 

    for(i=min;i<=max;i+=2)//checking only even numbers 
    { 
     cc=0; 
     for(j=2;j<i;j++)//avoiding dividing by 1 and itself 
     { 
      if(i%j==0)cc++; 
     } 
     if(pc<cc) 
     { 
      no=i; 
      pc=cc; 
     } 
    } 
    return no; 
} 

Answer 5

對於小的界限，使用篩子將是我的好處。從這個事實

  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，以及指數的相同多重集，但可能以不同的順序），那所有具有相同數量的約數，最小的是一個地方

• 的主要因素是r最小素數
• 的指數出現降序（2擁有最大的指數，3下一個最大的。 ..）

因此，我們可以通過考慮所有有限序列

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

與物業

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

和追捧號碼查詢最除數<= N最小的號碼是由它們產生的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個約數。我們獲得x_1 ≈ 8.3, x_2 ≈ 5.24。現在讓我們看看e_1, e_2接近x_1, x_2會發生什麼。

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

   偏離遠離比例減少除數快速計數，

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

   因此對最靠近的比例沒有產生最大除數計數，但那些與大除數計數是最接近的三個。

2. 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 = 80 
   2^5 *3^4*5^2 = 64800, τ(2^5 *3^4*5^2) = 6*5*3 = 90 
   2^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 = 84 
   2^7 *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 = 80 
   2^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 
   

   ，大除數計數爲指數達到接近相稱。

3. 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 = 108 
   

   對於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 = 80640, τ(2^8*3^2*5^1*7^1) = 9*3*2*2 = 108 
   2^9*3^1*5^1*7^1 = 53760, τ(2^9*3^1*5^1*7^1) = 10*2*2*2 = 80 
   

4. 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*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 
   2^6*3^1*5^1*7*11 = 73920, τ(2^6*3^1*5^1*7*11) = 7*2*2*2*2 = 112 
   

5. r = 6：由於2*3*5*7*11*13 = 30030，還有這裏只有一名候選人，

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

   ，併產生更小的除數比使用四個或五個素數的最佳候選人數多。

因此，我們研究了28名候選人（和可以跳過幾個）發現的最小數量<= 100000最除數爲83160（98280爲100000以下，128除數對方號碼）。

這是一個程序，它可以找到最小的數字，其最大除數不會超過給定的極限< 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"); 
}