znajdź liczbę z zakresu od 1 do 100, która ma najwięcej dzielników.

Question

Jak znaleźć najmniejszą liczbę z zakresu od 1 do 100, która ma najwięcej dzielników? Wiem, że trywialnym sposobem byłoby sprawdzenie dzielników każdej liczby od 1 do 100 i śledzenie liczby mającej maksymalny dzielnik. Ale czy jest bardziej efektywny sposób?

Answer 1

jest „łatwiejszy sposób”, ale jest to teoretyczna, nie bardzo algorytm komputerowy. Powstają dwa różne przypadki - jeden, jeśli przez "większość czynników" masz na myśli właśnie to, a drugi, jeśli czynniki muszą być unikalne.

W pierwszym przypadku wystarczy rozpoznać, że aby zmaksymalizować liczbę czynników, każdy czynnik musi być tak mały, jak to możliwe, tj. 2. Liczba mniejsza niż 100, która ma najwięcej czynników, jest zatem Największa moc 2 mniej niż 100, czyli 64.

Jeśli czynniki muszą być unikalne, to po prostu używamy 2, 3, 5 itd. (liczby pierwsze), dopóki następny skumulowany produkt nie będzie większy niż 100 - w tym przypadku 2 * 3 * 5 = 30 to liczba, która ma najbardziej unikalne czynniki. Dodanie czwartego czynnika sprawiłoby, że będzie on 210, a więc tak wysoki, jak to tylko możliwe.

Answer 2

Dla każdej liczby od 1 do 100 można sprawdzić wszystkie jej wielokrotności i dodać liczbę dzielników. W zależności od tego, w jaki sposób sprawdzasz dzielniki każdej liczby, może być bardziej efektywny. Oto kod Pythona, który realizuje ten pomysł. Złożoność wynosi 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))) 

A oto kod w 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); 

Obie wersje zachować maksymalną liczbę spośród wszystkich numerów z maksymalnymi dzielników. W tym przypadku 96 ma 12 dzielników.

Answer 3

Możesz wziąć jakiś pomysł z sita algorytmu Eratostenesa. Jedyną rzeczą jest to, że musisz uruchomić wewnętrzną pętlę od 2 * i zamiast * i. Ale ten algorytm jest szybszy niż 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]; 
} 

To daje 30 o liczbie dzielnik jako 3. Można modyfikować wewnętrzną pętlę jeśli chcesz warianty odpowiedź

Answer 4

Jednym ze sposobów być uniknąć numery nieparzyste ..

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

Dla małych ograniczeń, użycie sita byłoby wystarczające. Z faktu

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

oczywiste jest, że liczba dzielników można łatwo określić na podstawie głównego faktoryzacji n, a τ(m*n) = τ(m) * τ(n) jeśli gcd(m,n) = 1 (tj τ jest funkcji multiplikatywnej).

Więc możemy tanio obliczyć τ(n) jeśli wiemy wszelkich podstawowym czynnikiem n i wszystkie τ(m) dla 1 <= m < n.Zatem

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; 
    } 
} 

znajduje najmniejszą liczbę z największą dzielnik liczyć nieprzekraczającej N w O(N*log log N) czasie przy stosunkowo małej stałej współczynnik (które mogą być dalej redukowane przez traktowanie 2 oddzielnie tylko oznakowania nieparzystych wielokrotności nieparzystych liczb pierwszych).

Jest to prosta metoda brute-force, że jest wystarczająco szybki dla małych N (interpretacji „mały” zależy od pojęcia „dość szybko”, może być <= 1000 lub <= 1000000 na przykład).

Dla większych ograniczeń, jest to zbyt wolne i zbyt intensywne. W tym celu musimy wykonać nieco więcej analiz.

Od (1), możemy wywnioskować, że wśród wszystkich liczb o tej samej strukturze pierwotnej faktoryzacji (co oznacza tę samą liczbę r różnych czynników pierwotnych i tego samego multisetę wykładników, ale być może w innej kolejności), wszystkie mają taką samą liczbę dzielników, najmniejsza jest jeden gdzie

• głównymi czynnikami są r najmniejsze bodźce pojawiające
• wykładniki w kolejności malejącej (2 posiada największy wykładnik, 3 następna największa,. ..)

Więc możemy znaleźć najmniejszą liczbę z największą ilością dzielników <= N z uwzględnieniem wszystkich ciągów skończonych

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

z właściwością

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

i poszukiwanego numeru jest jednym z n(e_1, ..., e_r) produkowanego przez nich. (Jeśli n(e_i) <= N/2 o monotonicznie rosnącej skończonych dla sekwencji, sekwencja o 1 dodano do e_1 by wytwarzać z większą liczbę <= N dzielników).

Największa liczba dzielnik jest wytwarzany przez propagatorów, które są w przybliżeniu proporcjonalna do 1/log p_k. Dokładniej, na czas r, niech

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

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

Następnie T zakłada jej wartość maksymalną na zbiorze { x : F(x) = N and x_k > 0 for all k } w punkcie z

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

Tylko przyznać wykładników całkowitych, co komplikuje sprawę, ale odejście zbyt daleko od proporcjonalności produkuje liczby o mniejszej liczbie dzielników niż w pobliżu proporcjonalności.

Zilustrujmy to dla N = 100000 (to nieco zbyt mały, aby naprawdę wykorzystać proporcjonalność, ale wystarczająco małe, aby całkowicie zrobić ręcznie):

1. r = 1: e_1 = 16, n(16) = 2^16 = 65536 ma 17 dzielników.

2. r = 2: Ustawienie x_2 = x_1 * log 2/log 3 i N = 2^x_1 * 3^x_2 = 2^(2*x_1) otrzymujemy x_1 ≈ 8.3, x_2 ≈ 5.24.Zobaczmy teraz, co stanie się z e_1, e_2 blisko 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 
   

   odejście dalej od proporcjonalności zmniejsza dzielnik liczyć szybko,

   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 
   

   Więc najbliższa para do proporcjonalności nie produkują największą liczbę dzielnik, ale te z dużą liczbą dzielnik były najbliższe trzy.

3. r = 3: Podobnie otrzymujemy 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 
   

   ponownie, duże liczy dzielnik są osiągane dla wykładników blisko proporcjonalności.

4. r = 4: Zgrubne przybliżenia do wykładników to x_1 ≈ 4.15, x_2 ≈ 2.42, x_3 ≈ 1.79, x_4 ≈ 1.48. Dla e_4 = 2 istnieje tylko jeden wybór,

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

   dla e_4 = 1, mamy jeszcze kilka możliwości:

   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 
   

5. r = 5: x_1 ≈ 3.3, x_2 ≈ 2.1, x_3 ≈ 1.43, x_4 ≈ 1.18, x_5 ≈ 0.96. Od 2*3*5*7*11 = 2310, wykładniki z dnia 7 i 11 musi wynosić 1, znajdziemy kandydaci

   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 
   

6. r = 6: Od 2*3*5*7*11*13 = 30030 istnieje tylko jeden kandydat tutaj,

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

   i który wytwarza mniejszy dzielnik liczą niż najlepsi kandydaci używający czterech lub pięciu liczb pierwszych.

Więc zbadaliśmy 28 kandydatów (i mógł pominąć kilka z nich), aby stwierdzić, że najmniejsza liczba <= 100000 z największą ilością dzielników jest 83.160 (98.280 jest inna liczba poniżej 100 tysięcy z 128 dzielników).

Oto program, który znajdzie najmniejszą liczbę z największą liczbą dzielników nieprzekraczającą danego limitu < 2^64 praktycznie natychmiastowo (nie wykonano żadnych prób skrócenia, ponieważ jest wystarczająco szybki, jak dla 64-bitowych liczb całkowitych, dla dowolnych liczb całkowitych dokładności , które mogłyby stać się opłacalne w pewnym momencie):

#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"); 
}