Project Euler 193 - Squarefree Numbers

Official link:

Note: I am happy with my solution even if the runtime is ~100 seconds

Thought Process

I have absolutely no idea how this problem is 55% difficulty. After I solved Problem 745 which is 10% difficulty, I spent literally 3 mins to solve this one....

I used the exact same algorithm to find the number of non-squarefree numbers and then I just subtracted that from 2^50. My code runs in ~ 100 seconds which is technically out of acceptable range, but I know I am using an inefficient algorithm and I am confident in my understanding, so maybe I will re-do it in the future.

Edit: With new knowledge of the Mobius function I was able to shorten my previous solution from 100s to 40s, see my Essential Functions for the count_kfree function

Interactive Code

Enter a number (yourinput)

Code will output the number of squarefree numbers below yourinput