प्रोजेक्ट यूलर समस्या 12 - सी ++

Question

मैं 500 divisors के साथ पहले त्रिकोण संख्या के बारे में समस्या 12 पर काम कर रहा हूँ। मैंने समाधान को मजबूर करने की कोशिश की। मुझे लगभग 35 सेकंड में 300 divisors मिलते हैं और 10 मिनट के भीतर 400 नहीं मिल सकता है। मैं प्राइम फैक्टर विधि का उपयोग करने के लिए अपने समाधान को बदलने जा रहा हूं लेकिन मैंने अब देखा है कि लोग अभी भी एक मिनट के भीतर ब्रूट फोर्स के साथ इस समाधान को प्राप्त कर रहे हैं।

क्या आप कृपया मेरे कोड की आलोचना कर सकते हैं और मुझे बता सकते हैं कि क्या मुझे ऐसा कुछ याद आ रहा है जो इस बेहद अक्षम है?

unsigned long long TriangleNumberDivisors(int divisorTarget) 
{ 
    unsigned long long triangleNum=1; 
     unsigned long long currentNum=2; 
    int numOfDivisors=0; 


    numOfDivisors=NumOfDivisors(triangleNum); 
    while(numOfDivisors<divisorTarget) 
    { 
     triangleNum+=currentNum; 
     currentNum++; 
     numOfDivisors=NumOfDivisors(triangleNum); 
    } 

    return triangleNum; 
} 

int NumOfDivisors(unsigned long long dividend) 
{ 
    int numDivisors=0; 
    set<unsigned long long> divisors; 
    set<unsigned long long>::iterator it; 

    for(unsigned long long index=1; index<=dividend/2; index++) 
    { 
     if(dividend%index==0) 
     { 
      divisors.insert(index); 
      numDivisors++; 
      it=divisors.find(dividend/index); 
      if(it==divisors.end()) 
      { 
       divisors.insert(dividend/index); 
       numDivisors++; 
      } 
       /*for some reason not checking for dups above and 
just checking for how many items are in the set at the end is slower 
      for(it=divisors.begin();it!=divisors.end();it++) 
      { 
        numDivisors++; 
      } 
        */ 
     } 
    } 

    return numDivisors; 
} 

int main() 
{ 
    cout<<TriangleNumberDivisors(500)<<endl; 

    return 0; 
} 

अद्यतन: अब इसे प्राप्त करें, धन्यवाद। संख्या के वर्ग रूट की जांच करने के लिए बदल दिया गया, और यह देखने के लिए एक अतिरिक्त जांच की गई कि यह एक आदर्श वर्ग था या नहीं। इसने मुझे सेट को पूरी तरह से हटाने की अनुमति दी। 500 divisors 12 सेकंड में भाग गया।

Answer 1

वर्तमान में आप dividend/2 तक विभाजक की जांच करते हैं। आप इसे sqrt(dividend) पर कम कर सकते हैं, जो असम्बद्ध रूप से तेज़ है। dividend वर्ग है तो एक विशेष मामले की आवश्यकता हो सकती है।

मेरे सी ++ समस्या 12 के लिए कोड (जो अनिवार्य रूप से तुम्हारा के रूप में ही है, लेकिन यह कम सीमा का उपयोग करता है, और यह भी सिर्फ उन्हें सेट में भंडारण के बजाय divisors में गिना जाता है) लेता है के बारे में 1 सेकंड

Answer 2

for(unsigned long long index=1; index<=dividend/2; index++) 

मैं देखें कि आपने अपने लूप को dividend/2 पर dividend पर पुन: स्थापित करने के बजाय इसे अनुकूलित करने का प्रयास किया है। अपने आप को sqrt(dividend) तक सीमित करना बेहतर होगा (इस अर्थ में कि आप कम divisors की जांच कर रहे हैं)।

प्लस, यदि आप लाभांश के वर्ग रूट द्वारा स्वयं को सीमित करते हैं, तो आपको डुप्लिकेट डिवीजनों की जांच करने की आवश्यकता नहीं है। यह केवल वर्ग संख्याओं के लिए होगा, इसलिए डुप्लिकेट डालने से बचने के लिए केवल अनुक्रमणिका == लाभांश/अनुक्रमणिका जांचें।

Answer 3

मुझे यकीन नहीं है कि आपको divisors, set टाइप वैरिएबल, NumOfDivisors विधि में क्यों चाहिए। numDivisors क्यों गिनती है (sqrt(dividend) तक इंडेक्स के साथ) पर्याप्त नहीं है? (set एक संतुलित बाइनरी खोज पेड़ के रूप में लागू किया गया है, यह विधि को धीमा कर रहा है।)। इसके अलावा, ऐसा लगता है कि आप divisors.insert(..)दो बार का आह्वान कर रहे हैं।

Answer 4

ऐसा लगता है कि आप कुछ प्रदर्शन प्राप्त कर सकते हैं यदि आपने किसी विशेष संख्या के लिए विभाजक की संख्या को कैश किया था।