Can you help me optimize this code for finding factors of a number? I'm brushing up on my math programming.

Question

I've never really bothered with math programming, but today I've decided to give it a shot.

Here's my code and it's working as intended:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace PrimeFactorization
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        private void btnSubmit_Click(object sender, RoutedEventArgs e)
        {
            List<int> primeFactors = FindPrimeFactors(Convert.ToInt32(txtNumber.Text));
            primeFactors.Sort();
            for (int i = 0; i < primeFactors.Count; i++)
            {
                listBoxFoundNumbers.Items.Add(primeFactors[i]);
            }            
        }

        private List<int> FindPrimeFactors(int number)
        {
            List<int> factors = new List<int>();
            factors.Add(1);
            factors.Add(number);

            for (int i = 2; i < number; i++)
            {

                if (number % i == 0)
                {
                    int holder = number / i;
                    //If the number is in the list, don't add it again.
                    if (!factors.Contains(i))
                    {
                        factors.Add(i);
                    }
                    //If the number is in the list, don't add it again.
                    if (!factors.Contains(holder))
                    {
                        factors.Add(holder);
                    }
                }            
            }

            return factors;
        }
    }
}

The only problem I can see with my code is that it will iterate through to the bitter end, even though there will definitely not be any factors.

For example, imagine I wrote in 35. My loop will go up to 35 and check 24,25,26,27...etc. Not very good.

What do you recommend?

Answer 1

One thing you can do is avoid checking even numbers after 2, since they will never be prime.

So, check 2 and then declare your loop as such:

for (int i = 3; i < number; i+=2)

Re: stopping at sqrt(n) - this is an effective technique for determining whether a given number is prime, since any n that divides x where x > sqrt(n) also divides n/x which is necessarily less than sqrt(n). But a number may have prime factors larger than its own square root (for example, 1002 = 2 * 3 * 167).

That said, you could implement some kind of recursive solution where, for all prime factors p of n such that p < sqrt(n), you also calculate the prime factors of n / p. My gut feeling is that this will decrease the running time of your algorithm in general, but might increase it for small values of n.

Edit: if you're interested in getting into more sophisticated techniques, the Wikipedia page on Integer Factorization links to all kinds of algorithms.

Answer 2

You can go only up to and including sqrt(number). Consider x from 2 to sqrt(N). if N % x == 0, then N % (N / x) == 0 as well. Take 10 for example:

sqrt(10) = 3 (integer part).

10 % 2 == 0 => 2 is a divisor of 10. 10 % (10 / 2) == 10 % 5 == 0 => 5 is also a divisor.

10 % 3 != 0.

This is it, the divisors of 10 are 2 and 5. You have to be careful when dealing with perfect squares and that is it.

You also don't need your checks to see if a number is in the list or not if you do it like this. Just make sure you don't add the same number twice in case of perfect squares (if x == N / x, only add x).

This is about as efficient as it gets without considering a lot more complicated algorithms.

Edit: To get PRIME factors only, when you find an x such that N % x == 0, divide N by x while this is possible. For example, consider 20:

sqrt(20) = 4.

20 % 2 == 0 => 2 is a prime factor. Divide it by 2 until the remainder of the division by 2 is no longer 0: 20 / 2 = 10, 10 / 2 = 5.

5 % 3 != 0

5 % 4 != 0

The number you are left with at the end of the algorithm is 5 > 1, so add 5 as well. The prime factors of 20 are therefore 2 and 5.

So basically your algorithm in pseudocode is this:

listPrimes(number)
  N = number;
  for ( i = 2; i <= (int)sqrt(number); ++i )
    if ( N % i == 0 )
      primeFactors.Add(i);
      while ( N % i == 0 )
        N /= i;

  if ( N > 1 )
    primeFactors.Add(N);

You can also use what @danben has suggested in his post, using increments of 2 and starting from 3 and treating 2 separately. The most efficient however is to generate primes using the sieve of Eratosthenes and using those generated primes in combination with this algorithm. Most efficient while staying in the world of basic math anyway.

Answer 3

If you want to find all factors (not just prime), once you find a smallest factor, k, you can update your loop's upper bound to only go up to (and including) n/k. This is because the largest factor l must satisfy p = k * l.

An even better approach may be to use the factors that you've found so far to calculate the factors greater than sqrt(n). So, in the above, you could calculate l directly from k and n.

Answer 4

One classic algorithm for finding prime factors is the Sieve of Eratosthenes (see this)

Answer 5

First order of business is to use a proper prime-generating algorithm. Most common is the Sieve of Eratosthenes, which I'll post because it's easier, but there's also the Sieve of Atkin which is far more optimized.

I'd use something like this for the sieve, which I've posted before:

public class Primes
{
    public static IEnumerable<int> To(int maxValue)
    {
        if (maxValue < 2)
            return Enumerable.Empty<int>();

        bool[] primes = new bool[maxValue + 1];
        for (int i = 2; i <= maxValue; i++)
            primes[i] = true;

        for (int i = 2; i < Math.Sqrt(maxValue + 1) + 1; i++)
        {
            if (primes[i])
            {
                for (int j = i * i; j <= maxValue; j += i)
                    primes[j] = false;
            }
        }

        return Enumerable.Range(2, maxValue - 1).Where(i => primes[i]);
    }
}

The last step is just to find out which primes are factors, which is easy:

public static IEnumerable<int> GetPrimeFactors(int num)
{
    return Primes.To(num).Where(i => num % i == 0);
}

That's it! This will generate prime factors up to 20 million in less than 1 second, so it's probably good enough for whatever you're doing. Otherwise you can use a better sieve, as I mentioned at the top, or a lazy skip-set algorithm.

One last thing: If you're trying to factor huge numbers then you need to switch to something very different, such as the General Number Field Sieve. This is (as far as I know) currently the fastest factorization algorithm for very large numbers, as part of ongoing research to see if RSA encryption can be cracked.