Member Avatar for Member #899648

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.

  • 4 Contributors
  • 7 Replies
  • 244 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by Member #899648

Dani AI

Generated

Good catch on the integer-division issue and the need to both detect and remove factors (the core idea hinted at). Keep the code simple: pull out factor 2 repeatedly, then test odd divisors and remove them as you find them. Removing factors as you go shrinks the number and reduces the range you need to test. was right to point out that dividing integers truncates — use modulus (%) to test divisibility rather than rounding. ’s loop that checks every i up to n/2 is both unnecessary and can pick up composite “factors” instead of repeatedly removing prime factors.

A compact, robust C# implementation (uses long, avoids overflow by testing f <= n / f):

public static long LargestPrimeFactor(long n)
{
    if (n < 2) return -1;

    long max = -1;

    // remove all 2s
    while ((n & 1L) == 0)
    {
        max = 2;
        n >>= 1;
    }

    // try odd factors
    for (long f = 3; f <= n / f; f += 2)
    {
        while (n % f == 0)
        {
            max = f;
            n /= f;
        }
    }

    // if remainder > 1 it's prime
    if (n > 1) max = n;

    return max;
}

Notes and tips: use long for the Project Euler input (600851475143 fits). To handle numbers larger than 64-bit, switch to System.Numerics.BigInteger and a safe trial-division loop. Test with small numbers (edge cases like n <= 1) to be sure your logic handles them. For 600851475143 this method yields 6857 and runs in negligible time on a modern machine.

Recommended Answers

All 7 Replies

Member Avatar for Member #899648

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

Member Avatar for 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.

Member Avatar for 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 :)

Edited by Momerath because: n/a
Member Avatar for 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.

Edited by skatamatic because: Noticed some inefficiency
Member Avatar for 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?

Member Avatar for 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)

Edited by skatamatic because: n/a
Member Avatar for Member #899648

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.