Official link: https://projecteuler.net/problem=634
Note: For some reason, I cannot figure out why I am off by 1 on some answers, but I'm more than happy with my implementation
This problem was very interesting and I had to learn a lot of new concepts.
The first and most important step to solving this problem is finding out about Powerful Numbers which are numbers that can be expressed as a^2*b^3 but a or b can be 1, very similar to what our question wants.
We get our first hint on the page which is that a^2*b^3 can be uniquely represented if b is squarefree, therefore we come up with the following:
Point 1 can be easily done with a Mobius Sieve, I made a function for this (and it is generalised) it is in my Essential Functions.
Point 2 was the crux of the problem, to efficiently find the number of cube-free numbers. I thought we could generalise the Mobius Function, and at first I wrongfully applied it until I found Aposotols Generalised Mobius Function.
Using this we can easily find not only cube-free but k-free integers, this function was also added to my Essential Functions Page as well as mathslib.
Putting everything together, we have a very elegant equation for the final problem, π is the prime counting function
Input an integer (yourinput)
Code will output F(yourinput)
Note: The answer could be 1 or 2 off the actual correct answer