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!