StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POOut of Memory error finding products and primes
text
Body
copied!<p>So I wrote a quick app to check my son's homework and it appears to be working fine. It takes a number, finds all the primes, then finds all the product combinations. So, for example, you pass it "210", and it will return:<br/> 2 x 3 x 5 x 7<br/> 5 x 6 x 7<br/> 7 x 30<br/> 6 x 35<br/> 5 x 42<br/> 3 x 7 x 10<br/> 10 x 21<br/> 3 x 70<br/> 3 x 5 x 14<br/> 14 x 15<br/> 2 x 7 x 15<br/> 2 x 105<br/> 2 x 5 x 21<br/> 2 x 3 x 35<br/></p> <p>The problem I'm having is when doing large numbers. It will handle 256 (2^8) after only a moment's hesitation, but when I do 512 (2^9), I get a OutOfMemoryException. Can someone recommend a better way of finding the product sets? My code is below.</p> <pre><code>class Program { private static List<List<int>> coll = new List<List<int>>(); public static List<int> PrimeFactors(int i) { if (i < 2) { throw new ArgumentOutOfRangeException("Numbers less than 2 don't have prime factors"); } List<int> result = new List<int>(); int divisor = 2; while (divisor <= i) { if (i % divisor == 0) { result.Add(divisor); i /= divisor; } else { divisor++; } } return result; } private static void GetFactors(List<int> l) { for (int i = 0; i < l.Count - 1; i++) { for (int x = i + 1; x < l.Count; x++) { List<int> loopList = new List<int>(l); int newProd = l[i] * l[x]; loopList.RemoveAt(i); loopList.RemoveAt(x-1); loopList.Add(newProd); loopList.Sort(); coll.Add(loopList); if (loopList.Count > 2) { GetFactors(loopList); } } } } static void Main(string[] args) { int target = Convert.ToInt16(args[0]); List<int> results = PrimeFactors(target); results.Sort(); coll.Add(results); GetFactors(results); List<string> factors = new List<string>(); foreach (List<int> lst in coll) { string listString = ""; for (int i = 0; i < lst.Count; i++) { if (i == lst.Count - 1) { listString += String.Format("{0}", lst[i]); } else { listString += String.Format("{0} x ", lst[i]); } } factors.Add(listString); } foreach (String factorString in factors.Select(x => x).Distinct()) { Console.WriteLine(factorString); } } } </code></pre> <p>EDIT: Here is the new code, based on answers below. Works for any Int16 I throw at it.</p> <pre><code> class Program { private static List<List<int>> coll = new List<List<int>>(); public static List<int> PrimeFactors(int i) { if (i < 2) { throw new ArgumentOutOfRangeException("Numbers less than 2 don't have prime factors"); } List<int> result = new List<int>(); int divisor = 2; while (divisor <= i) { if (i % divisor == 0) { result.Add(divisor); i /= divisor; } else { divisor++; } } return result; } private static void GetFactors(List<int> l) { for (int i = 0; i < l.Count - 1; i++) { for (int x = i + 1; x < l.Count; x++) { List<int> loopList = new List<int>(l); int newProd = l[i] * l[x]; loopList.RemoveAt(i); loopList.RemoveAt(x-1); loopList.Add(newProd); bool existsInCollection = false; foreach (List<int> existingList in coll) { if (ListEquality(existingList, loopList)) { existsInCollection = true; break; } } if (!existsInCollection) { coll.Add(loopList); if (loopList.Count > 2) { GetFactors(loopList); } } } } } private static bool ListEquality(List<int> listA, List<int> listB) { if (listA.Count != listB.Count) return false; listA.Sort(); listB.Sort(); for (int idx = 0; idx < listA.Count; idx++) { if (listA[idx] != listB[idx]) return false; } return true; } static void Main(string[] args) { int target = Convert.ToInt16(args[0]); List<int> results = PrimeFactors(target); results.Sort(); coll.Add(results); GetFactors(results); foreach (List<int> lst in coll) { string listString = ""; for (int i = 0; i < lst.Count; i++) { if (i == lst.Count - 1) { listString += String.Format("{0}", lst[i]); } else { listString += String.Format("{0} x ", lst[i]); } } Console.WriteLine(listString); } } } </code></pre> <p>Thanks again to everyone.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload