किसी संख्या के कारक प्राप्त करना

Question

समस्या: मैं इसे तेजी से बनाने के लिए इस एल्गोरिदम को दोबारा करने की कोशिश कर रहा हूं। गति के लिए यहां पहला रिफैक्टरिंग क्या होगा?

public int GetHowManyFactors(int numberToCheck) 
    { 
     // we know 1 is a factor and the numberToCheck 
     int factorCount = 2; 
     // start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor 
     for (int i = 2; i < numberToCheck; i++) 
     { 
      if (numberToCheck % i == 0) 
       factorCount++; 
     } 
     return factorCount; 
    } 

Answer 1

पहला अनुकूलन जो आप कर सकते हैं वह है कि आपको केवल संख्या के वर्ग रूट की जांच करने की आवश्यकता है। ऐसा इसलिए है क्योंकि कारक जोड़े में आते हैं जहां एक वर्ग रूट से कम होता है और दूसरा बड़ा होता है।

यह एक अपवाद है यदि n एक सटीक वर्ग है तो इसकी वर्ग रूट n का एक कारक है लेकिन एक जोड़ी का हिस्सा नहीं है।

उदाहरण के लिए यदि आपका नंबर 30 कारकों है इन जोड़ों में कर रहे हैं:

• 1 x 30
• 2 एक्स 15
• 3 x 10
• 5 x 6

तो आपको 5 से अधिक संख्याओं की जांच करने की आवश्यकता नहीं है क्योंकि जोड़ी में इसी छोटे कारक को खोजने के बाद अन्य सभी कारकों को पहले ही अस्तित्व में ले जाया जा सकता है।

यहाँ एक तरह से सी # में यह करने के लिए है:

public int GetFactorCount(int numberToCheck) 
{ 
    int factorCount = 0; 
    int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck)); 

    // Start from 1 as we want our method to also work when numberToCheck is 0 or 1. 
    for (int i = 1; i < sqrt; i++) 
    { 
     if (numberToCheck % i == 0) 
     { 
      factorCount += 2; // We found a pair of factors. 
     } 
    } 

    // Check if our number is an exact square. 
    if (sqrt * sqrt == numberToCheck) 
    { 
     factorCount++; 
    } 

    return factorCount; 
} 

वहाँ अन्य तरीकों आप इस्तेमाल कर सकते हैं कि तेजी से कर रहे हैं, लेकिन आपको पता चल सकता है कि यह पहले से ही अपनी आवश्यकताओं के लिए काफी तेजी से है, खासकर यदि आप केवल जरूरत है यह 32-बिट पूर्णांक के साथ काम करने के लिए।

Answer 2

आप कैसे उच्च के रूप में आप जानबूझकर, संख्या का वर्गमूल पर रोक सकता है, हालांकि यह वर्गों है कि कारकों में से विषम संख्या के लिए होता है चुनने की सावधानी ले करता है जाना है के लिए बाध्य को कम करना है, लेकिन यह कम करने में मदद करता है कि लूप को कितनी बार निष्पादित किया जाना है।

Answer 3

1. आप numberToCheck/2 के लिए अपने लिए पाश की ऊपरी सीमा को सीमित कर सकते

2. 2 में अपने पाश काउंटर शुरू (अपना नंबर भी है) या (विषम मूल्यों के लिए) 3। यह आपको अपने लूप गिनती को 50% तक छोड़ने वाले हर दूसरे नंबर की जांच करने की अनुमति दे सकता है।

   public int GetHowManyFactors(int numberToCheck) 
   { 
       // we know 1 is a factor and the numberToCheck 
       int factorCount = 2; 
   
       int i = 2 + (numberToCheck % 2); //start at 2 (or 3 if numberToCheck is odd) 
   
       for(; i < numberToCheck/2; i+=2) 
       { 
       if (numberToCheck % i == 0) 
        factorCount++; 
       } 
       return factorCount; 
   } 
   

Answer 4

ऐसा लगता है कि इस सटीक विषय के बारे में यहाँ एक लंबी चर्चा है की तरह: Algorithm to calculate the number of divisors of a given number

आशा इस

Answer 5

में मदद करता है ठीक है तो आप इस समारोह एक बहुत आप संशोधित उपयोग कर सकते हैं का उपयोग करने के लिए जा रहे हैं, तो Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes के एल्गोरिदम और सरणी में 1 से अधिकतम अंतराल के लिए Answars स्टोर करें। यह IntializeArray() को एक बार चलाएगा और उसके बाद 0 (1) में जवाब वापस कर देगा।

const int Max =1000000; 
int arr [] = new int [Max+1]; 

public void InitializeArray() 
{ 
    for(int i=1;i<=Max;++i) 
     arr[i]=1;//1 is factor for everyone 

    for(int i=2;i<=Max;++i) 
     for(int j=i;i<=Max;i+=j) 
      ++arr[j]; 
} 
public int GetHowManyFactors(int numberToCheck) 
{ 
    return arr[numberToCheck]; 
} 

लेकिन अगर आप इस समारोह एक बहुत उपयोग करने के लिए नहीं जा रहे हैं मुझे लगता है कि सबसे अच्छा समाधान वर्गमूल unitll जाँच करने के लिए है।

---

नोट: मैंने अपना कोड सही कर दिया है!

Answer 6

नोटिस करने वाली पहली बात यह है कि यह सभी प्रमुख कारकों को खोजने के लिए पर्याप्त है। एक बार आपके पास इन्हें कुल divisors की संख्या को ढूंढना आसान हो जाता है: प्रत्येक प्राइम के लिए, 1 बार दिखाई देने वाली संख्या में जोड़ें और इन्हें एक साथ गुणा करें। तो 12 = 2 * 2 * 3 के लिए आपके पास (2 + 1) * (1 + 1) = 3 * 2 = 6 कारक हैं।

अगली चीज़ पहले से निम्न होती है: जब आपको कोई कारक मिल जाता है, तो इसे विभाजित करें ताकि परिणामी संख्या छोटी हो। जब आप इसे इस तथ्य से जोड़ते हैं कि आपको केवल वर्तमान संख्या के वर्ग रूट की जांच करने की आवश्यकता है, यह एक बड़ा सुधार है। उदाहरण के लिए, एन = 10714293844487412 पर विचार करें। नैतिक रूप से यह एन कदम उठाएगा। इसकी वर्ग रूट तक जांचने से एसकर्ट (एन) या लगभग 100 मिलियन कदम उठते हैं। लेकिन चूंकि कारक 2, 2, 3, और 953 की खोज शुरुआती है, वास्तव में आपको केवल एक मिलियन की जांच करने की आवश्यकता है - 100x सुधार!

एक और सुधार: आपको यह देखने के लिए हर नंबर की जांच करने की आवश्यकता नहीं है कि यह आपके नंबर को विभाजित करता है, केवल प्राइम्स। यदि यह अधिक सुविधाजनक है तो आप 2 और विषम संख्याओं, या 2, 3, और संख्या 6 एन -1 और 6 एन + 1 (एक मूल पहिया चलनी) का उपयोग कर सकते हैं।

यहां एक और अच्छा सुधार है। यदि आप जल्दी से निर्धारित कर सकते हैं कि कोई संख्या प्रमुख है, तो आप विभाजन की आवश्यकता को और भी कम कर सकते हैं। मान लीजिए, छोटे कारकों को हटाने के बाद, आपके पास 120528291333090808192969 है। यहां तक ​​कि इसके वर्ग रूट तक की जांच करने में काफी समय लगेगा - 300 अरब कदम। लेकिन एक मिलर-राबिन परीक्षण (बहुत तेज - शायद 10 से 20 नैनोसेकंड) दिखाएगा कि यह संख्या समग्र है। यह कैसे मदद करता है? इसका मतलब यह है कि यदि आप इसकी घन रूट की जांच करते हैं और कोई कारक नहीं पाते हैं, तो वास्तव में दो प्राइम शेष हैं। यदि संख्या एक वर्ग है, तो इसके कारक प्रमुख हैं; यदि संख्या वर्ग नहीं है, तो संख्याएं अलग-अलग प्राइम हैं। इसका मतलब यह है कि आप अंतिम जवाब प्राप्त करने के लिए क्रमशः 3 या 4 तक अपने 'रनिंग कुल' को गुणा कर सकते हैं - यहां तक ​​कि कारकों को जानने के बिना भी! इससे अनुमान लगाए जाने से अधिक अंतर हो सकता है: 300 अरब से केवल 50 मिलियन तक की जरूरतों की संख्या, 6000 गुना सुधार!

उपरोक्त के साथ एकमात्र परेशानी यह है कि मिलर-राबिन केवल साबित कर सकता है कि संख्याएं समग्र हैं; अगर इसे एक प्रधान दिया जाता है तो यह साबित नहीं कर सकता कि संख्या प्रमुख है। उस स्थिति में आप संख्या के वर्ग रूट पर फैक्टरिंग के प्रयास को छोड़ने के लिए एक प्राथमिकता-सिद्ध कार्य लिखना चाह सकते हैं। (वैकल्पिक रूप से, आप कुछ और मिलर-राबिन परीक्षण कर सकते हैं, अगर आप उच्च आत्मविश्वास से संतुष्ट होंगे कि आपका उत्तर एक सबूत के बजाय सही है। यदि कोई संख्या 15 परीक्षण पास करती है तो यह 1 से कम संभावना के साथ समग्र है । एक अरब में)

Answer 7

एल्गोरिथ्म है कि आप परीक्षण विभाजन की तुलना में बहुत आगे लाना होगा लागू करने के लिए एक आसान Pollard Rho

यहाँ एक जावा कार्यान्वयन है, कि सी # के लिए अनुकूल करने के लिए आसान होना चाहिए है: http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html

Answer 8

https://codility.com/demo/results/demoAAW2WH-MGF/

public int solution(int n) { 
     var counter = 0;   
     if (n == 1) return 1; 
     counter = 2; //1 and itself  
     int sqrtPoint = (Int32)(Math.Truncate(Math.Sqrt(n))); 
     for (int i = 2; i <= sqrtPoint; i++) 
     { 
     if (n % i == 0) 
     { 
      counter += 2; // We found a pair of factors.   
     }  
     } 
     // Check if our number is an exact square. 
     if (sqrtPoint * sqrtPoint == n) 
     { 
     counter -=1; 
     } 

     return counter; 
    }