除数が最も多い1から100の範囲の最小数を見つける方法は？簡単な方法は、1から100までの各数値の除数をチェックし、最大除数を持つ数値を追跡することです。しかし、もっと効率的な方法はありますか？
質問する
9696 次
5 に答える
3
小さめの境界では、ふるいを使用するだけで十分です。事実から
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;
}
}
比較的小さい定数係数で、最大の除数数NがO(N*log log N)時間内に超えない最小の数を見つけます（2を別々に扱い、奇数の素数の奇数の倍数のみをマークすることでさらに減らすことができます）。
これは、小さい場合に十分な速さの単純なブルートフォース方式ですN（「小さい」の解釈は、「十分に速い」の概念に依存します。たとえば、次のようになります）<= 1000。<= 1000000
より大きな境界の場合、それは遅すぎてメモリを大量に消費します。それらについては、もう少し分析を行う必要があります。
r（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)彼らによって生み出されたものの1つです。（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（比例関係を実際に活用するには少し小さすぎますが、手作業で完全に活用するには小さすぎます）：
r = 1：e_1 = 16、n(16) = 2^16 = 6553617の約数があります。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ます。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したがって、比例に最も近いペアは最大の除数カウントを生成しませんでしたが、除数カウントが大きいペアは最も近い3つでした。
r = 3：同様に、x_1 ≈ 5.5, x_2 ≈ 3.5, x_3 ≈ 2.42^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この場合も、比例に近い指数に対して大きな除数カウントが達成されます。
r = 4：指数の大まかな近似はx_1 ≈ 4.15, x_2 ≈ 2.42, x_3 ≈ 1.79, x_4 ≈ 1.48です。の場合e_4 = 2、選択肢は1つだけです。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 = 80r = 5：x_1 ≈ 3.3, x_2 ≈ 2.1, x_3 ≈ 1.43, x_4 ≈ 1.18, x_5 ≈ 0.96。、7と11の指数は1でなければならないので2*3*5*7*11 = 2310、候補を見つけます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 = 112r = 6：以来2*3*5*7*11*13 = 30030、ここには候補が1つだけあります。2^2*3*5*7*11*13 = 60060, τ(60060) = 3*2^5 = 96これにより、4つまたは5つの素数を使用する最良の候補よりも除数の数が少なくなります。
そこで、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");
}
于 2012-12-04T23:36:41.920 に答える
2
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の除数があります。
于 2012-12-04T18:00:25.463 に答える
1
「より簡単な方法」がありますが、それは理論的なものであり、実際にはコンピューターアルゴリズムではありません。2つの異なるケースが発生します。1つは「ほとんどの要因」がそれだけを意味する場合、もう1つは要因が一意である必要がある場合です。
最初のケースでは、因子の数を最大化するには、各因子をできるだけ小さくする必要があることを認識する必要があります。つまり、2です。したがって、因子が最も多い100未満の数は、2の最大の累乗です。 100未満、たまたま64です。
因子が一意でなければならない場合は、次の累積積が100を超えるまで、2、3、5など（素数）を使用します。この場合、2 * 3 * 5=30は最もユニークな要因。4番目の要素を追加すると210になるので、可能な限り高くなります。
于 2012-12-04T18:18:34.737 に答える
0
エラトステネスのアルゴリズムのふるいからいくつかのアイデアを得ることができます。唯一のことは、i*iではなく2*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];
}
これにより、除数の数が3の30が得られます。回答にバリアントが必要な場合は、内部ループを変更できます。
于 2012-12-04T18:11:34.800 に答える
0
1つの方法は、奇数を避けることです。
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;
}
于 2012-12-04T18:17:56.697 に答える