Project Euler problem#3 - can anyone help me understand why my code doesn't work
Does anyone know why my code below doesn't work? Is the variable n too large? I tried a smaller number from the example '13195' and was able to get it to work but when I tried the question number my program freezes when I run it.
This is the question: The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Thank you
This is the question: The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
|
|
Thank you
Last edited on
Your algorithm is very inefficient. Your program doesn't freeze; it's just got an enormous amount of work to do. Part of the point of Project Euler is for you to think about the mathematics behind what you're doing and come up with efficient algorithms.
For example, your function isPrime.
Take a number. Let's say 100. Your function then calculates 100%99. That won't be zero, will it? Then, 100%98. Another wasted, expensive operation.
It's obvious that any number over half of 100 isn't worth checking. But you check them all! So many wasted, expensive operations.
Your isPrime function doesn't even do the really simple check that the number is even. ANy even number greater than 2 isn't prime, but your code will check 600851475142 for primeness, and take a really long time doing it.
Basically, what's wrong with your code is that it's very inefficient and will take a very very long time.
For example, your function isPrime.
Take a number. Let's say 100. Your function then calculates 100%99. That won't be zero, will it? Then, 100%98. Another wasted, expensive operation.
It's obvious that any number over half of 100 isn't worth checking. But you check them all! So many wasted, expensive operations.
Your isPrime function doesn't even do the really simple check that the number is even. ANy even number greater than 2 isn't prime, but your code will check 600851475142 for primeness, and take a really long time doing it.
Basically, what's wrong with your code is that it's very inefficient and will take a very very long time.
On line 3 you should use a long long for the loop variable, int is too small for n
Maybe your program doesn't hang, it might take very long.
You could try to add some print statements to see what you program is doing.
Maybe your program doesn't hang, it might take very long.
You could try to add some print statements to see what you program is doing.
Just looking at the number 600851475143 I know straight away that the largest factor possible can not be above 600851475143 / 2 , because the largest possible factor for any number would be if the number was 2 x largest_possible_factor. So there is no point checking any number from above 600851475143 / 2 , but your code is checking them all. Even though we know none of them will be a factor. Your code checks three hundred billion values that we know cannot be the answer before it gets to 600851475143 / 2 . Three hundred billion expensive checks.
Each one of those checks goes through the function isPrime. That function then carries out possibly as many modulus checks as the number itself; so before we even get to possible answers, your code conducts on the order of
300000000000 squared ( not quite that, it's 300000000000 + 2999999999999 + 2999999999998 + ... + 1)
expensive factorial operations, which is about 10^23 operations. If each one takes a nanosecond, it's a couple of million years.
I am sure someone will come aong shortly and get all OCD on these numbers, but the point is that you will die before your program finishes.
Each one of those checks goes through the function isPrime. That function then carries out possibly as many modulus checks as the number itself; so before we even get to possible answers, your code conducts on the order of
300000000000 squared ( not quite that, it's 300000000000 + 2999999999999 + 2999999999998 + ... + 1)
expensive factorial operations, which is about 10^23 operations. If each one takes a nanosecond, it's a couple of million years.
I am sure someone will come aong shortly and get all OCD on these numbers, but the point is that you will die before your program finishes.
Last edited on
@Pilly, I guess it has already been said, but the main problem with your algorithm is that it will take too long to run.
Some better strategies:
- You are looking for the largest prime factor. So you started testing large numbers and worked down. But this is not a good idea. It is quick to test small numbers for primeness: if you find one of these you can divide out by this factor. This will rapidly reduce n.
- A better algorithm is simply to work upwards from the smallest number and test whether n divides by that number; divide out by each factor as you find them. The smallest factor (other than 1) of a positive integer must always be prime. As you remove these factors your problem will get smaller.
- If your number is odd, then you can start looking for factors at 3 and go up in steps of 2, since no even number can be a factor.
That took a fraction of a second. Imagine how long it would take to test every number from 600851475143 down to 6857 for primeness.
Some better strategies:
- You are looking for the largest prime factor. So you started testing large numbers and worked down. But this is not a good idea. It is quick to test small numbers for primeness: if you find one of these you can divide out by this factor. This will rapidly reduce n.
- A better algorithm is simply to work upwards from the smallest number and test whether n divides by that number; divide out by each factor as you find them. The smallest factor (other than 1) of a positive integer must always be prime. As you remove these factors your problem will get smaller.
- If your number is odd, then you can start looking for factors at 3 and go up in steps of 2, since no even number can be a factor.
600851475143 = 71 x 839 x 1471 x 6857 |
That took a fraction of a second. Imagine how long it would take to test every number from 600851475143 down to 6857 for primeness.
| That took a fraction of a second. Imagine how long it would take to test every number from 600851475143 down to 6857 for primeness. |
Ahem :D Using the original algorithm, a couple of million years, by my potentially wrong very rough back-of-envelope calculation!
Off-topic, this, of course, is one of the key lessons Project Euler is teaching. That you don't have infinite processing power, that understanding the problem is key to solving it, and that programming is about how you think about problems and their solutions. Memorising the syntax is like learning how to write; it doesn't make one a novelist, it just means one is ready to start learning.
Last edited on
Topic archived. No new replies allowed.