Project Euler 549 - Divisibility of factorials
Official link: https://projecteuler.net/problem=549
Note: My code takes around ~230s
One useful formula that set me on the right path was Legendre's Formula which introduces a quick way to to get the prime factorisation of huge factorials, otherwise I notice the following.
Now the problem is how to efficiently compute s(p^e), but this itself is not too difficult
If e = 1 then s(p^e) = p
If e = 2 then s(p^e) = m, where m has at least 2 factors of p, so we need only check if multiples of p factorial are divisible by p^e, and this gives us a very quick way to calculate
However, the problem was not as simple as I thought, this method alone quickly gives an answer for 10^6, but is still much too slow for 10^8. After about 3 attempts at making it as fast as possible I managed to get the answer in ~230 seconds, which is still too slow. I did this by generating all the primes less that 10^8, and then storing all s(p^e) in an array and then using that array to sieve the rest of the numbers.
I believe I can sieve everything in one go, instead of essentially doing it twice, to vastly increase the speed.
Enter an integer (yourinput) < 10^6 because otherwise it will take too long
Code will output S(yourinput)