patterncsharpMinor
Project Euler Problem 3: Largest prime factor
Viewed 0 times
problemlargestprojecteulerfactorprime
Problem
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
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
{} 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 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;
}
}Solution
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:
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.
More good naming.
Why
What is the point of the right side of the ||? How can
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
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:
Can you implement such a method? If you can, then you can reimplement
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.
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 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.
Code Snippets
static long LargestPrimeFactor(long number)long largestFactor = 1;for (long i = 2; i<= Math.Sqrt(number); i++)static bool IsFactorOf(long numerator, long denominator)
{
return numerator % denominator == 0 || numerator == denominator;
}static bool IsPrime(long value)
{Context
StackExchange Code Review Q#163216, answer score: 7
Revisions (0)
No revisions yet.