CODEWITHSUNDEEP
c#prime-factoring
Vlad
Vlad

Reputation: 618

Largest Prime Factor algorithm optimization

I'm trying to improve this interesting algorithm as much as I can.

For now, I have this:

using System;

class Program
{

    static void Main()
    {
        ulong num, largest_pFact;
        uint i = 2;
        string strNum;

        Console.Write("Enter number: ");
        strNum = Console.ReadLine();
        num = ulong.Parse(strNum);
        largest_pFact = num;


        while (i < Math.Sqrt((double) largest_pFact))
        {
            if (i % 2 != 0 | i == 2) {
                if (largest_pFact % i == 0) 
                    largest_pFact /= i;
            }

            i++;
        }

        Console.WriteLine("Largest prime factor of {0} is: {1}", num, largest_pFact);
        Console.ReadLine();

    }
}

So any ideas?

Thanks!

EDIT: I implemented Ben's algorithm, thanks eveyone for your help!

Upvotes: 1

Views: 3786

Answers (6)

Justin Morgan
Justin Morgan

Reputation: 30760

For one thing, you don't need to run Math.Sqrt on every iteration.

    int root = Math.Sqrt((double) largest_pFact);

    while (i < root)
    {
        if ((i % 2 != 0 | i == 2) && largest_pFact % i == 0) {
            largest_pFact /= i;
            root = Math.Sqrt((double) largest_pFact);
        }

        i++;
    }

Upvotes: 1

Ben Voigt
Ben Voigt

Reputation: 283644

I've got a faster algorithm here.

It eliminates the square root and handles repeated factors correctly.

Optimizing further:

static private ulong maxfactor (ulong n)
{
    unchecked
    {
        while (n > 3 && 0 == (n & 1)) n >>= 1;

        uint k = 3;
        ulong k2 = 9;
        ulong delta = 16;
        while (k2 <= n)
        {
            if (n % k == 0)
            {
                n /= k;
            }
            else
            {
                k += 2;
                if (k2 + delta < delta) return n;
                k2 += delta;
                delta += 8;
            }
        }
    }

    return n;
}

Here's a working demo: http://ideone.com/SIcIL

Upvotes: 2

Guffa
Guffa

Reputation: 700342

Well, first I would move the special case 2 out of the loop, there is no point in checking for that throughout the loop when it can be handled once. If possible use the data type int rather than uint, as it's generally faster:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
while (i < Math.Sqrt((double) largest_pFact)) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

The square root calculation is relatively expensive, so that should also be done beforehand:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

Then I would increment i in steps of two, to elliminate one modulo check:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

To work, I believe that you need a while instead of an if inside the loop, otherwise it will skip factors that are repeated:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  while (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

Upvotes: 1

khedoros
khedoros

Reputation: 46

It's always faster to look between sqrt(num) and 2 than it is to start at num/2. Every factor pair (besides the square-root one) has one number that is less than sqrt(num).

Ex: For 15, int(sqrt(15))==3 15/3=5, so you found the "5" factor by starting your testing at 3 instead of 7.

Upvotes: 0

damienix
damienix

Reputation: 6763

I think:

  • generate primes up to num/2
  • then check from largest to lowest if your num is divisible by the prime

would be faster.

edit num/2 NOT sqrt

Upvotes: 0

Jems
Jems

Reputation: 11620

-Store Math.Sqrt((double) largest_pFact) in some variable, preferably a ulong. That avoids recalculating the function every pass through the loop, and integer comparison may be faster than floating-point comparisons. You will need to change the comparison to a <= though.

-Avoid looping on even numbers at all. Just include a special case for i=2, and then start with i at 3, incrementing by 2 on each loop. You can go even further by letting i=2,3 be special cases, and then only testing i = 6n+1 or 6n-1.

Upvotes: 1

Related Questions