3
\$\begingroup\$

The problem statement is as follows. I feel as if my code can be improved but I'm not able to see how to do so. Is there merit in removing {} on the if blocks? Since I'm new, could that unintentionally lead to bugs if I forget that only a single instruction can be executed?

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

What is the largest prime factor of the number 600851475143 ?

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(LargestPrimeFactor(600851475143)); 
        Console.ReadLine();
    }

    static long LargestPrimeFactor(long number)
    {
        long largestFactor = 1;

        for (long i = 2; i<= Math.Sqrt(number); i++)
        {
            if (IsFactorOf(number, i))
            {
                if (IsPrime(i))
                {
                    largestFactor = i;
                }

                while (number > 1 && IsFactorOf(number, i))
                {
                    number /= i;
                }
            }
        }

        if (number == 1)
        {
            return largestFactor;
        }
        else
        {
            return number;
        }
            
    }

    static bool IsFactorOf(long numerator, long denominator)
    {
        return numerator % denominator == 0 || numerator == denominator;
    }        

    static bool IsPrime(long value)
    {
        int maxPossibleRoot = (int)Math.Sqrt(value);
        for (int i = 2; i <= maxPossibleRoot; i++)
        {
            if (value % i == 0)
            {
                return false;
            }
        }
        return true;
    }
}
\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

Is there merit in removing {} on the if blocks?

If you are the kind of person who is likely to write bugs without the braces, then leave them in.

Other notes:

static long LargestPrimeFactor(long number)

Good naming.

Long will do you for the first few Euler problems but you might have to install System.Numerics and use BigInteger for some problems coming up soon.

long largestFactor = 1;

More good naming.

for (long i = 2; i<= Math.Sqrt(number); i++)

i is not descriptive. possibleFactor perhaps?

i <= Math.Sqrt(number) is much slower than i * i <= number.

static bool IsFactorOf(long numerator, long denominator)
{
    return numerator % denominator == 0 || numerator == denominator;
}  

Why numerator and denominator? There are no fractions.

What is the point of the right side of the ||? How can !(n%d==0) and (n==d) both be true?

static bool IsPrime(long value)
{

Your implementation is adequate now, but will be too slow for later problems. Think about how you might optimize this. For example: if you've already checked divisibility by 2, then why are you checking 4, 6 and 8?

But more generally: Under what circumstances in your existing implementation is IsPrime ever false? Suppose you are factorizing 840.

You start by throwing out the twos -- a prime -- and get down to 105. Then you throw out the threes -- a prime -- and get down to 35. Then you check fours -- why? You've already checked twos, so four cannot be a factor. Then you check fives, you have a factor, and surprise, 5 is a prime.

Your algorithm only finds prime factors because it has already thrown out all the composite factors who have smaller factors! So you don't have to check for primality at all in your algorithm.

Finally: you don't need it for this problem, but for later problems you will benefit greatly from having a method:

static IEnumerable<long> PrimeFactors(long number)

Can you implement such a method? If you can, then you can reimplement

static long LargestPrimeFactor(long number)
{
  return PrimeFactors(number).Max();
}

and you're done. In Euler problems it often pays to solve a more general problem, and then write a query against the more general solution.

\$\endgroup\$
2
  • \$\begingroup\$ RE: "i <= Math.Sqrt(number) is much slower than i * i <= number" How would I determine that? Is there a rule of thumb to follow (IE: methods are slower than operation?) RE: "There are no fractions." I should have used the words dividend and divisor instead. RE: "||" from my previous attempt at having it return the correct value. It was returning the second largest prime. I've been trying to solve for the more general problems in anticipation of harder problems and to stretch my programming abilities. Thanks for your helpful critiques, it really helps. \$\endgroup\$
    – IvenBach
    May 13, 2017 at 3:59
  • 2
    \$\begingroup\$ @IvenBach: To determine if one bit of code is slower than another, write it both ways and run it, and see which takes longer. But this should be clear from first principles; how long does it take you to multiply two numbers vs how long does it take you to compute a square root? \$\endgroup\$ May 13, 2017 at 6:48

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.