श्रेणी 1 से 100 में संख्या खोजें जिसमें सबसे अधिक विभाजक

Question

सबसे विभाजित करने वाले 1 से 100 की श्रेणी में सबसे छोटी संख्या को कैसे ढूंढें? मुझे पता है कि प्रत्येक संख्या के divisors को 1 से 100 तक जांचने के लिए एक छोटा रास्ता होगा और अधिकतम divisor वाले नंबर का ट्रैक रखें। लेकिन क्या कोई और अधिक प्रभावी तरीका है?

Answer 1

एक "आसान तरीका है" वहाँ है, लेकिन यह सैद्धांतिक है, वास्तव में नहीं एक ऐसे कंप्यूटर एल्गोरिदम। दो अलग-अलग मामले सामने आते हैं - एक यदि "अधिकांश कारकों" से आपका मतलब है, और दूसरा यदि कारकों को अद्वितीय होना चाहिए।

पहले मामले में, आपको केवल यह पहचानने की आवश्यकता है कि, कारकों की संख्या को अधिकतम करने के लिए, प्रत्येक कारक को जितना संभव हो उतना छोटा होना चाहिए, यानी 2. 100 से कम संख्या में सबसे अधिक कारक हैं, इस प्रकार यह है 100 से कम 2 की सबसे बड़ी शक्ति, जो 64 होती है।

यदि कारक अद्वितीय होना चाहिए, तो हम केवल 2, 3, 5, आदि (मुख्य संख्या) का उपयोग करते हैं जब तक कि अगले संचयी उत्पाद अधिक से अधिक न हो 100 - इस मामले में 2 * 3 * 5 = 30 वह संख्या है जिसमें सबसे अद्वितीय कारक हैं। चौथा कारक जोड़ने से यह 210 हो जाएगा, इसलिए जितना ऊंचा हो उतना उतना ऊंचा हो सकता है।

Answer 2

प्रत्येक नंबर के लिए 1 से 100 तक आप इसके सभी गुणों को देख सकते हैं और divisors की संख्या जोड़ सकते हैं। प्रत्येक नंबर के divisors की जांच कैसे कर रहे हैं, इस पर निर्भर करता है, यह अधिक कुशल हो सकता है। यहां एक पायथन कोड है जो इस विचार को करता है। जटिलता हे है (एन लॉग ऑन एन)

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))) 

और यहाँ सी

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

में कोड दोनों संस्करणों अधिकतम divisors के साथ सभी नंबरों से बाहर अधिकतम संख्या रखना है। इस मामले में 96 में 12 विभाजक हैं।

Answer 3

आप एराटोस्टेनेस एल्गोरिदम की चलनी से कुछ विचार ले सकते हैं। केवल बात यह है कि आपको 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. के रूप में आप आंतरिक पाश संशोधित कर सकते हैं अगर आप इस सवाल का जवाब में वेरिएंट

Answer 4

एक ही रास्ता होगा चाहते भाजक की संख्या के साथ 30 देता है हो विषम संख्या से बचने के लिए ..

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 

से यह स्पष्ट है कि divisors की संख्या आसानी से n के प्रधानमंत्री गुणनखंड से निर्धारित किया जा सकता है, और उस τ(m*n) = τ(m) * τ(n) अगर gcd(m,n) = 1 (अर्थात τ एक गुणक समारोह है)।

तो हम सस्ते में गणना कर सकता है τ(n) अगर हम n के किसी भी प्रधानमंत्री कारक और 1 <= m < n के लिए सभी τ(m) पता है।इस प्रकार

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, और एक्सपोनेंट का एक ही बहुआयामी, लेकिन संभवतः विभिन्न क्रम में), सभी, divisors के एक ही नंबर है, छोटी से छोटी से एक है जहां

• अभाज्य गुणकों r छोटी से छोटी अभाज्य संख्या घटते क्रम में
• एक्स्पोनेंट्स दिखाई (2 सबसे बड़ा प्रतिपादक, 3 अगला सबसे बड़ा है कर रहे हैं। ..)

,210

तो हम संपत्ति

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

और मांग की संख्या के साथ सभी परिमित दृश्यों

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

पर विचार करके सबसे divisors <= N साथ सबसे छोटी संख्या पा सकते हैं n(e_1, ..., e_r) उनके द्वारा उत्पादित से एक है। (यदि एक monotonic गैर बढ़ती परिमित अनुक्रम के लिए n(e_i) <= N/2, 1 के साथ अनुक्रम e_1 को जोड़ा अधिक divisors के साथ एक नंबर <= 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

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

हम केवल पूर्णांक घातांक है, जो इस मामले को पेचीदा स्वीकार करते हैं, लेकिन भटक साथ बिंदु में सेट { x : F(x) = N and x_k > 0 for all k } पर इसके अधिक से अधिक मूल्य मान लिया गया है आनुपातिकता से बहुत दूर अनुपात की तुलना में कम divisors के साथ संख्या पैदा करता है।

की यह 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 प्राप्त करते हैं।अब देखते हैं कि e_1, e_2x_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.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 
   

   फिर से प्राप्त करने, बड़े भाजक मायने रखता है समानता के करीब घातांक के लिए हासिल कर रहे हैं।

4. 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 
   

5. 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 
   

6. r = 6: 2*3*5*7*11*13 = 30030 के बाद से, वहाँ केवल एक ही यहाँ उम्मीदवार है,

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

   और कहा कि एक छोटे भाजक का उत्पादन चार या पांच प्राइम का उपयोग कर सर्वश्रेष्ठ उम्मीदवारों की तुलना में गिनें।

तो हम 28 उम्मीदवारों की जांच की (और उनमें से कई को छोड़ दिया हो सकता है) है कि ज्यादातर divisors के साथ सबसे छोटी संख्या <= 100000 83,160 है खोजने के लिए (98280 100000 128 के साथ divisors नीचे अन्य संख्या है)।

यहां एक ऐसा प्रोग्राम है जो सबसे अधिक विभाजक के साथ सबसे छोटी संख्या को < 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"); 
}