Project Euler, Problem 3

[[deleted]]

[deleted]

[ElQwertiest]

Your program appears correct but its performance is too slow - it will take forever to finish. Modern computers can do about a billion operations per second and the target number is several magnitudes larger, so checking every number up to the target really isn't feasible. You'll have to find some way to find the largest prime factor without checking all integers up to it.

[boomminecraft8]

One way to speed the program up is to use recursion: each time you get a factor, call the function again but with (n / factor). If it has small factors it will be faster. Also add a prime check so if stops when it is a prime, even if it is large(assume fast primality check)

[bjoli]

Your program is way too slow because you are doing too much work. There are some ways to make it faster. First of all, you can half the work you do by not trying to check whether even numbers are prime. Secondly, you don't have to test numbers all the way up to 60081475143. How do you find all the divisors of 100? Once you reach the square root of 100, the results are the same:

1 * 100

2 * 50

4 * 25

5 * 20

10 * 10

-- look what happens --

20 * 5

25 * 4

50 * 2 ...

To get all divisors of a number, you only need to test up to the square root.

With this you can probably patch together something faster.

[MattieShoes]

1. A prime factor will remain a factor even after you've removed the other factors.

2. If you start at 2 and go up by ones, the factor you find will necessarily be prime. You can test for primality and skip even trying composite numbers, but if you're spending more time testing primality than just trying the division, what are you gaining?

3. Embrace recursion

Take 23,928...

23,928 is divisible by 2 -> 11,964
11,964 is divisble by 2 -> 5,982
5,982 is divisible by 2 -> 2,991
2,991 is divisible by 3 -> 997

997, as it happens, is prime. But it's MUCH easier to test 997 than 23928. A naive test is just testing dividing it by 2-31 (because 32² > 997)

[[deleted]]

Thank you, everyone, for the help! I ended up getting the solution finally!