संभव डुप्लिकेट:
Efficiently finding all divisors of a numberसबसे कुशल तरीका एक नंबर के सभी divisors पाने के लिए
यह एक सामान्य की तुलना में एक दक्षता सवाल का बहुत अधिक है "यह करने के लिए एक रास्ता खोजने "है, लेकिन कुछ अजीब परिणाम प्राप्त करने के बाद, मैं देखने के लिए अगर किसी ने मुझे बता सकते हैं चाहता हूँ क्यों पिछले रास्ता तो अक्षम है:
तरीका 1: जानवर बल, कोई अनुकूलन
+०१२३५१६४१०public static List<int> proper_divisors(int x)
{
List<int> toreturn = new List<int>();
for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
{
if (x % i == 0)
{
toreturn.Add(i);
toreturn.Add(x/i);
}
}
if (toreturn.ElementAt(toreturn.Count()/2) == toreturn.ElementAt(toreturn.Count()/2 - 1))
{
toreturn.Remove(toreturn.ElementAt(toreturn.Count()/2));
}
return toreturn;
}
रास्ता 2: पहले की तरह ही, लेकिन इस बार, अगर जाँच अपने प्रधानमंत्री पहले
public static List<int> proper_divisors(int x)
{
List<int> toreturn = new List<int>();
if (!isprime(x))
{
for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
{
if (x % i == 0)
{
toreturn.Add(i);
toreturn.Add(x/i);
}
}
if (toreturn.ElementAt(toreturn.Count()/2) == toreturn.ElementAt(toreturn.Count()/2 - 1))
{
toreturn.Remove(toreturn.ElementAt(toreturn.Count()/2));
}
}
else
{
toreturn.Add(1);
toreturn.Add(x);
}
return toreturn;
}
यह क्या सोचा है (जैसा कि उन मामलों में प्रधानमंत्री की जाँच के लिए मिलर-राबिन का उपयोग कर, सबसे अधिक समय तक का समय लग) दूर तक 3 तक का सबसे तेज़ तरीका होगा, क्योंकि यह उस संख्या को कम करता है जब यह हर बार एक प्रमुख कारक पाया जाता है, और यह केवल प्राइम की कोशिश करता है (इन्हें रनटाइम पर चलने से उत्पन्न किया गया था, लगभग 34 एमएस प्राप्त करने के लिए सभी प्राइम एक लाख से भी कम) इस तरह की आखिरी चीज को प्रमुख कारकों और उनकी शक्तियों को लेना था, और सभी कारकों की एक सूची बनाना था।
रास्ता 3: तरीका 1:
public static HashSet<int> prime_factors(int x)
{
if (!isprime(x))
{
List<int> toreturn = new List<int>();
int i = 0;
while (primes[i] <= x)
{
if (x % primes[i] == 0)
{
toreturn.Add(primes[i]);
x = x/primes[i];
}
else
{
i++;
}
}
var power_set_primes = GetPowerSet(toreturn);
var factors = new HashSet<int>();
foreach (var p in power_set_primes)
{
var factor = p.Select(z => z).Aggregate(1, (z, y) => z * y);
factors.Add(factor);
}
return factors;
}
else
{
HashSet<int> toreturn = new HashSet<int>();
toreturn.Add(1);
toreturn.Add(x);
return toreturn;
}
public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
return from m in Enumerable.Range(0, 1 << list.Count)
select
from i in Enumerable.Range(0, list.Count)
where (m & (1 << i)) != 0
select list[i];
}
समय यह पहली मिलियन संख्या कारक ले लिया 7223 एमएस रास्ता 2: 8985 एमएस (प्रधानमंत्री जाँच छोटी संख्या के लिए इसके लायक नहीं है मैं लगता है) रास्ता 3: 4 9 423 एमएस
तो मेरा प्रश्न दो गुना है: 1) रास्ता 3 इतना धीमा क्यों है ??? 2) क्या ऐसा कुछ है जो इसे तेज़ी से बना सकता है? एक तरफ के रूप में, प्राइम्स को एक सूची के रूप में गणना की गई थी, फिर एक सरणी में परिवर्तित किया गया, जैसा कि मैंने सोचा था कि यह तेज़ होगा। गलत कदम?
क्या आपने पहले से यह नहीं पूछा था? http://stackoverflow.com/questions/5793009/efficiently-finding-all-divisors-of-a-number –
प्रोफाइल प्रोफ़ाइल प्रोफ़ाइल। इसके अलावा, अगर आप वहां दक्षता की परवाह करते हैं तो एन्युमेटर या LINQ का उपयोग न करें। इसे सी में लिखें और पी/Invoke का उपयोग करें। आम तौर पर, सवाल पूछें कि क्या आप इसे – sehe
माप सकते हैं कृपया "toreturn" के बजाय "परिणाम" जैसे कुछ का उपयोग करें। – MrFox