StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<pre><code>using System.Collections; public static int[] PrimeFactors(int num) { ArrayList factors = new ArrayList(); bool alreadyCounted = false; while (num % 2 == 0) { if (alreadyCounted == false) { factors.Add(2); alreadyCounted = true; } num = num / 2; } int divisor = 3; alreadyCounted = false; while (divisor <= num) { if (num % divisor == 0) { if (alreadyCounted == false) { factors.Add(divisor); alreadyCounted = true; } num = num / divisor; } else { alreadyCounted = false; divisor += 2; } } int[] returnFactors = (int[])factors.ToArray(typeof(int)); return returnFactors; } </code></pre> <p>I just copied and posted some code from <a href="http://www.smokycogs.com/blog/finding-the-prime-factors-of-a-number-in-c-sharp/" rel="nofollow">Smokey Cogs</a> because this is a very common problem. </p> <p>The code does some things better than yours.</p> <p>First you divide by two until the number is no longer even. From there, you can start with 3 and increment by 2 (skip every even number) since all the 2's have been factored out.</p> <p>Nonetheless, there are ways to improve. Think about the usage of "alreadyCounted" in the code. Is it absolutely essential? For example, using </p> <pre><code> if (num % 2 == 0) { factors.Add(2); num = num/2; } while( num %2 == 0) {num = num/2;} </code></pre> <p>Allows you to skip the extra comparisons in the beginning.</p> <p>RiaD also gave a great heuristic that <code>factor^2 > num</code> implies that num is prime. This is because <code>(sqrt(n))^2 = n</code>, so the only number after <code>sqrt(n)</code> that divides <code>num</code> will be <code>num</code> itself, once you've taken out the previous primes.</p> <p>Hope it helps!</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