Project Euler Question 3 Help
Solution 1
For starters, instead of beginning your search at n / 2, start it at the square root of n. You'll get half of the factors, the other half being their complement.
eg:
n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.
Solution 2
Although the question asks for the largest prime factor, it doesn't necessarily mean you have to find that one first...
Solution 3
long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3;
while( n > 1)
{
if(n % factor == 0)
{
n/=factor;
}else
factor += 2; //skip even numbrs
}
print factor;
This should be quick enough...Notice, there's no need to check for prime...
Solution 4
Actually, for this case you don't need to check for primality, just remove the factors you find. Start with n == 2 and scan upwards. When evil-big-number % n == 0, divide evil-big-number by n and continue with smaller-evil-number. Stop when n >= sqrt(big-evil-number).
Should not take more than a few seconds on any modern machine.
Solution 5
You need to reduce the amount of checking you are doing ... think about what numbers you need to test.
For a better approach read up on the Sieve of Erathosthenes ... it should get you pointed in the right direction.
Related videos on Youtube
Ryan Rodemoyer
Updated on April 19, 2022Comments
-
Ryan Rodemoyer about 2 years
I'm trying to work through Project Euler and I'm hitting a barrier on problem 03. I have an algorithm that works for smaller numbers, but problem 3 uses a very, very large number.
Problem 03: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
Here is my solution in C# and it's been running for I think close to an hour. I'm not looking for an answer because I do actually want to solve this myself. Mainly just looking for some help.
static void Main(string[] args) { const long n = 600851475143; //const long n = 13195; long count, half, largestPrime = 0; bool IsAPrime; half = n / 2; for (long i = half; i > 1 && largestPrime == 0; i--) { if (n % i == 0) { // these are factors of n count = 1; IsAPrime = true; while (++count < i && IsAPrime) { if (i % count == 0) { // does a factor of n have a factor? (not prime) IsAPrime = false; } } if (IsAPrime) { largestPrime = i; } } } Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + "."); Console.ReadLine(); }
-
Lemon almost 14 yearsIf you are interested, I solved this using the Sieve of Erasthosenes and a simple GetPrimeFactors method -- geekality.net/2009/09/17/project-euler-problem-3
-
-
Ryan Rodemoyer over 15 yearsI changed my starting point to this: startAt = (long)Math.Floor(Math.Sqrt(n)); and that gave me an immediate answer. Thanks!
-
Ryan Rodemoyer over 15 yearsI originally looked into this but I think I had a couple problems. I was trying to generate a list from 1...n and I was running out of memory. I do need to implement this though because I am sure it is going to come in handy in these problems.
-
Ian G over 15 yearsAnd is massively overkill for this sort of thing. If OP can't work out how do this quickly with simple tests I don't fancy his chances of getting Miller-Rabin working easily.
-
Rob Walker over 15 yearsWhen N is that high you would need to do things in slices: use an array to compute the primes 1 ... 1,000,000 then use these and rerun the algorithm between 1,000,000 and 2,000,000 .. etc. This will keep the memory to a fixed bound.
-
Jim C over 15 yearsThis method finds the factor of the number, but it will include both prime and not prime numbers. For example 9 is not prime.
-
Kirk Strauser over 15 yearsOnce you find 3, you set n = n / 3 = 9 and repeat from there.
-
Sundar R over 15 yearsThat exactly is the approach I too took to solve this one. I've given a description of the algorithm and some code (in perl) in my blog (thetaoishere.blogspot.com/2008/05/…). My runtime was only around 14 ms or so (in perl)...
-
PhirePhly over 15 yearsI agree, finding the smaller prime factors will be easier and reduce the problem space.
-
nickf over 15 years@Jim: Yep, that would be the first part of the question. To find the prime factors, you also gotta find the factors. Though, I guess you could do it the other way around and find the primes first. @JSG: Why would you do that?
-
Nicholas Mancuso over 15 yearstrue, but a lot of the PE problems involve primes. So writing a subprogram once to handle determining primality will be helpful in the long run.
-
jfs over 15 years@nickf: Starting at floor(sqrt(n-1)) is not safe e.g. 25: floor(sqrt(24)) = 4, is 4 a factor? no, 3? no, 2? no. Thus 5 is missed.
-
nickf over 15 yearsoh - that was a typo sorry. It's not supposed to be sqrt(n - 1). I've fixed that now.
-
TraumaPony over 15 yearsOr do it lazily; for example using a generative iterator.
-
simion almost 14 yearsthanks - i realise this post is old but still! i suck at maths but enjoy programming and hate being beaten by problems, if it wasnt for this post i would have been going for another 3 months !!!
-
JesperE almost 14 yearsThis is the beauty of SO being optimized to allow people to find good answers to old questions.
-
Manolete over 12 yearsWhat about 600851? The square root is ~775 however, there is a prime number 20719
-
nickf over 12 years@Manolete I don't understand your question.
-
Andrei Fierbinteanu over 12 years@Manolete going down from 775 you would eventually reach 29, and dividing 600851 by 29 you would see that 20719 is the other prime factor (complement)
-
Pratt over 11 yearsThe worst case complexity of this approach would still be O(sqrt(big-evil-number)) if "big-evil-number" is prime. I dont think this is an acceptable solution
-
JesperE over 11 yearsWhy isn't it acceptable? The task is not to implement a general prime number factorization function, the task is to find the largest prime factor of the given number.