Project Euler 193 - Squarefree Numbers
Official link: https://projecteuler.net/problem=193
Note: I am happy with my solution even if the runtime is ~100 seconds
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
Enter a number (yourinput)
Code will output the number of squarefree numbers below yourinput