9
\$\begingroup\$

Okay, so just having a little fun I thought I'd see if I could write an algorithm to find all of the prime factors of a number. The solution I came up with is as follows:

class Program
{
    static void Main(string[] args)
    {
        var subject = long.MaxValue;
        var factors = new List<long>();
        var maxFactor = 0;

        Console.WriteLine("Factoring {0} ...", subject);

        var sw = new Stopwatch();
        sw.Start();

        while (subject > 1)
        {
            var nextFactor = 2;
            if (subject % nextFactor > 0)
            {
                nextFactor = 3;
                do
                {
                    if (subject % nextFactor == 0)
                    {
                        break;
                    }

                    nextFactor += 2;
                } while (nextFactor < subject);
            }

            subject /= nextFactor;
            factors.Add(nextFactor);
            if (nextFactor > maxFactor)
            {
                maxFactor = nextFactor;
            }
        }

        sw.Stop();

        var factorAnswer = 1L;
        factors.ForEach(f => factorAnswer *= f);

        Console.WriteLine("Factors: {0} = {1}",
            string.Join(" * ",
                factors.Select(i => i.ToString()).ToArray()),
            factorAnswer);
        Console.WriteLine("Max Factor: {0}", maxFactor);
        Console.WriteLine("Elapsed Time: {0}ms", sw.ElapsedMilliseconds);
    }
}

and its output is:

Factoring 9223372036854775807 ...
Factors: 7 * 7 * 73 * 127 * 337 * 92737 * 649657 = 9223372036854775807
Max Factor: 649657
Elapsed Time: 3ms

It works, and IMO awfully fast, but it's a little brute force. Is there a better way of doing it?

\$\endgroup\$
0

2 Answers 2

12
\$\begingroup\$

Other algorithms

Wikipedia has an article which lists other Factoring algorithms.


Your algorithm

Re. your algorithm, I see you're checking all odd numbers, which includes non-prime numbers such as 9.

Your sieve would be faster if you only checked prime numbers, for example by using a list like this one or this one.

Furthermore you're checking all the way to subject. Your last time through the loop would be faster if you give up as soon as nextFactor > sqrt(subject).


Your C# code

As for your C# code:

  • What type is nextFactor when you declare it as var nextFactor = 2;? I fear that it might be int not long.
  • Your code might be very slightly faster if you used the Capacity property of List.
  • There's something very strange (and slow) about your loop: after you find a nextFactor value such as 7, then you begin your search from 2 again! You code would be faster if you moved your long nextFactor = 2; initialization to do it only once, before/outside the while loop, and changed your nextFactor = 3; statement to nextFactor += (nextFactor == 2) ? 1 : 2;. You could then also eliminate your maxFactor variable, because the largest factor value would be left/stored in nextValue after you exit the while loop.
  • It might be better to use System.Numerics.BigInteger instead of long (because long.MaxValue is only about 10^18, whereas some people want to factorize larger numbers than that).
\$\endgroup\$
7
  • \$\begingroup\$ What do you mean by that Capacity remark? I don't see how would it help here. \$\endgroup\$
    – svick
    Jan 31, 2014 at 21:15
  • \$\begingroup\$ Just that factors.Add might be ever-so-slightly slower if List has to reallocate internal memory instead of having enough Capacity from the moment it's constructed? \$\endgroup\$
    – ChrisW
    Jan 31, 2014 at 21:16
  • 1
    \$\begingroup\$ For the example 2^63-1, that Add was executed 7 times, while nextFactor += 2 something like 300 000 times. I think the Add won't measurably affect the overall performance. \$\endgroup\$
    – svick
    Feb 1, 2014 at 0:40
  • 1
    \$\begingroup\$ @svick I don't think it's very important either; I'm just trying to be thorough. The behaviour would be different if the subject were exactly 2^62 ... Add would be executed 62 times and might dominate the performance. \$\endgroup\$
    – ChrisW
    Feb 1, 2014 at 0:45
  • 1
    \$\begingroup\$ For 32-bit integers there really isn't anything much faster than just brute-forcing all primes under 65536. For 64-bit integers you might gain some performance by doing a quick sieve for these factors and then using Fermat's or Pollard's p - 1 to weed out the larger ones. Up to 256-300 bits the Rho algorithm (cycle finding) is probably optimal. After that you should pull out the big guns with ECM, QS, NFS, ... and eventually you are screwed because there is no known polynomial-time general purpose factoring algorithm. But implementing these is a great exercise! \$\endgroup\$
    – Thomas
    Feb 1, 2014 at 5:46
9
\$\begingroup\$

Code

Your code seems fine.

Like @ChrisW highlighted, take care about types. Your variables nextFactor and maxFactor are actually integers.

Also, string.Join can take objects - it will call ToString() internally. You can convert string.Join(" * ", factors.Select(i => i.ToString()).ToArray()) to string.Join(" * ", factors)

Algorithm

I suggest 2 improvements to the algorithm.

You are re-iterating values that you already discarded as not being factors.

If 2 is not a factor of subject on the first iteration, it will never be. So when you find a new factor X, on the next iteration you can continue looking for factors from X upwards - instead of re-checking the already-discarded values [2..X].

You only need to check until nextFactor*nextFactor>subject

And then the last factor is actually subject itself. :)
Right now, you check until nextFactor==subject (thus next iteration subject==1).

Explanation:

if subject is e.g. 21 and nextFactor is 11... since no number smaller than 11 is a factor, then all its factors are bigger or equal to 11.

  • If subject has one factor, that factor must be the subject itself (21);
  • If it has more than one, and because its factors are at least as big as 11, then 21>=X*Y, X>=11, and Y>=11.
    (X being the next factor, and Y being the next subject.)

So, in the case where nextFactor*nextFactor > subject, you know that the last factor has to be subject itself, and you can terminate processing earlier.

\$\endgroup\$
1
  • \$\begingroup\$ Beware of overflow with nextFactor*nextFactor > subject; consider a safer alternative (like the C++ greater_than_sqrt() function in Find perfect and amicable numbers). \$\endgroup\$ Aug 26 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.