कारकों की संख्या पाएं

Question

यह कोड किसी संख्या के कारकों का योग क्यों देता है?

कई परियोजना यूलर समस्याओं में, आपको समस्या के एक हिस्से के रूप में कारकों की राशि की गणना करने के लिए कहा जाता है। वहां पर एक मंच पर, किसी ने निम्न जावा कोड को उस योग को खोजने का सबसे अच्छा तरीका बताया है, क्योंकि आपको वास्तव में व्यक्तिगत कारकों को नहीं ढूंढना है, केवल प्रमुख (आपको जावा को जानने की आवश्यकता नहीं है, आपको नीचे दिए गए मेरे सारांश पर जा सकते हैं):

public int sumOfDivisors(int n) 
{ 
    int prod=1; 
    for(int k=2;k*k<=n;k++){ 
     int p=1; 
     while(n%k==0){ 
      p=p*k+1; 
      n/=k; 
     } 
     prod*=p; 
    } 
    if(n>1) 
     prod*=1+n; 
    return prod; 
} 

अब, मैंने इसे कई बार कोशिश की है और मुझे लगता है कि यह काम करता है। सवाल यह है, क्यों?

कहें कि आप 100: 1,2,4,5,10,20,25,50,100 पर कारक हैं। योग 217 है। मुख्य कारक 2*2*5*5 है। यह फ़ंक्शन आपको [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

फैक्टरिंग 8: 1,2,4,8 देता है। योग 15 है। मुख्य कारक 2*2*2 है। इस समारोह आप [2*(2*(2+1)+1)+1]=15

देता एल्गोरिथ्म (Fi का उपयोग कर कारक एफ या एफ उप मैं के ith सूचकांक मतलब करने के लिए) करने पर निर्भर करता:

return product(sum(Fi^k, k from 0 to Ni), i from 1 to m) 

जहां m अद्वितीय प्रधानमंत्री कारकों की संख्या है, Ni है प्राइम फैक्टरेशन में प्रत्येक अद्वितीय कारक की संख्या होती है।

यह सूत्र कारकों के योग के बराबर क्यों है? मेरा अनुमान है कि यह वितरक संपत्ति के माध्यम से प्रमुख कारकों (यानी हर अद्वितीय कारक) के हर अद्वितीय संयोजन के योग के बराबर है, लेकिन मुझे नहीं पता कि कैसे।

Answer 1

चलिए सबसे सरल मामले को देखते हैं: जब n एक प्रमुख संख्या की शक्ति है।

k^m के कारक 1, के, के^2, के^3 ... के^एम -1 हैं।

अब एल्गोरिथ्म के भीतरी पाश को देखो:

पहले यात्रा के बाद, हम k + 1 है।

दूसरी यात्रा के बाद, हम k(k+1) + 1, या k^2 + k + 1

तीसरे यात्रा के बाद, हम k^3 + k^2 + k + 1

और इसी तरह की है है ...

---

कि यह कैसे संख्या के लिए काम करता है जो एक ही प्रधान की शक्तियां हैं। मैं बैठ सकता हूं और इसे सभी नंबरों पर सामान्यीकृत कर सकता हूं, लेकिन हो सकता है कि आप इसे पहले स्वयं को छोड़ दें।

संपादित करें: अब यह स्वीकार्य उत्तर है, मैं यह दिखाकर थोड़ा और विस्तार करूंगा कि एल्गोरिदम दो विशिष्ट प्राइम कारकों के साथ संख्याओं पर कैसे काम करता है। यह सामान्यीकृत करने के लिए सरल है कि विशिष्ट प्राइम कारकों की मनमानी मात्रा के साथ संख्याओं के लिए।

x^i.y^j के कारकों x^0.y^0, x^0.y^1 ... x^0.y^j, x^1.y^0 रहे हैं ...

प्रत्येक विशिष्ट प्राइम फैक्टर के लिए आंतरिक लूप x^i + x^i-1 + ... + x^0 उत्पन्न करता है (और इसी तरह y के लिए)। फिर हम उन्हें एक साथ गुणा करते हैं और हमारे पास हमारे कारक हैं।

Answer 2

एल्गोरिथ्म अनिवार्य रूप से n, जो n के कारकों में से सेट के अनुरूप है के प्रधानमंत्री सभी कारकों के आदेश दिया सबसेट के सेट में दिख रही है।