Project Euler 642 - Sum of Largest Prime Factors

Official link: https://projecteuler.net/problem=642

Thought Process

This was a really difficult problem for me and took a lot of time and research.

I had a few ideas

201,820,182,018 is so large that I was expecting a O(sqrt(n)) type of algorithm
For a given prime p, can I find all numbers i such that f(i) = p

After some research I remembered n-Smooth numbers

Now I needed a way to calculate s(n, p). Having solved Project Euler Problem 204 I went through the threads to find a fast way to do this and I found a great post which I link here, have a look once you have solved the problem yourself! (Don't look further if you don't want spoilers for that problem)

Now I could design my first "good" algorithm, by splitting the primes into the ones greater than and less than sqrt(N)

Note that π1(n) is the sum of primes function an for this I used the extremely famous Lucy_Hedgehogs Method from Project Euler Problem 10. However, the recursion needed to calculate F1(n) was too much and I couldn't get the solution like this but it gave me the idea for a solution that actually worked!

And now I could solve the problem!

Interactive Code

Input an Integer (yourinput)

Code will output F(yourinput) (mod 1,000,000,000)

Page updated

Google Sites

Report abuse