Find the Largest Prime Factor of a Composite Number?

[Falcon25]

Hi everyone. I'm new(ish) to C# and i've decided to hone my skills in windows forms applications. I've got stuck on this question and would really appreciate some expertise from you guys:

"The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?"

The question is taken from projecteuler.net which has some challenging problems on their (not an advertisement) just saying incase anyone didn't know about the site. I've created this method which doesn't work around the while loop. The math.Round(i) doesn't work because i don't know how to use it, I read somewhere that it collects only whole numbers but I am unsure what I should be referencing.

private static long question3()
        {
            long bigNum = 600851475143;
            int x = 1;

            while (bigNum == Math.Round(bigNum))
            {
                bigNum /= x;
                x++;
            }
            return (bigNum);
        }

What i'm trying to do is to get this method to break down the 600851475143 then extract the largest whole number. I then wanted to put the largest whole varible into another method which would then further break down the number into its highest prime factor. I'm sure theres an easier way to do this, but please understand that i'm just practising and making mistakes as I go whilst trying to figure them out myself, but this has made me very confused. I would greatly appreciate help from you guys and maybe you could tell me the way you would tackle this problem. Thanks.

[Falcon25]

Just realised Math.Round() isn't what I should be using. This question is doing my head in

[ddanbe]

long bigNum = 7;
bigNum /= 2;

After this bigNum will be 3, so you don't have to round!
With two integers the / operator does integer division.

[Momerath]

You need to consider what it means to factor a number (and in this case, prime factor a number).

Once you understand that you'll need:

• A loop
• A way to test if a number is a factor
• A way to remove the factor from the number you are trying to factor.

P.S. If your program is taking more than 1 millisecond to run, you are doing it wrong :)

[skatamatic]

Not the most efficient algorithm, but pretty simple and self explanatory:

public long GetLargestPrimeFactor(long lNum)
        {
            List<int> iFactors = new List<int>();
            //Get all the prime factors
            for (int i = 1; i <= lNum / 2; i++)
                if (lNum % i == 0)
                {
                    iFactors.Add(i);
                    lNum /= i;
                }
            return iFactors.Count > 0 ? iFactors[iFactors.count-1] /*highest index is the highest prime factor*/ : -1;//No prime factors!
        }

I have a feeling that there is a nice way to get the div and mod into one operation and save about half the CPU time. Still, this can factor 600851475143 in less than a quarter of a second.

[Momerath]

Not the most efficient algorithm, but pretty simple and self explanatory

And wrong :) What's the largest prime factor of 24 using this method?

[skatamatic]

And wrong :) What's the largest prime factor of 24 using this method?

Lol crap. Apparently I forgot what a prime factor is. This just looks for a factor with a prime number in it! (Not both numbers)

[Falcon25]

Thanks guys, realised its more my mathematical skills letting me down on this question but thanks for the help