# Project Euler #193: Squarefree Numbers

# Project Euler #193: Squarefree Numbers

+ 0 comments I completed the problem, and while interesting, the difficulty level surely needs to be increased to at the very least, hard, if not advanced. I had to use a sublinear algorithm for the mertens function to get under the time limit. Unless there is an easier way that I happened to miss (or a way that wasn't compatible with the time-constraints for Julia), I find it a little ridiculous that a problem that requires a sublinear algorithm for the Mertens function be considered a medium difficulty problem. (Yes, that's a bit of a spoiler but it was released five years ago so I feel that's acceptable now.) The edge-cases were also a little silly...

+ 0 comments My code is passing 0 and 1 test cases but failing reaminig all test cases can anyone one help me out. My code is absolutely fine but i don't know why its failing test cases. def prime(k): for i in range(2,k): if k%i==0: return False return True

n,m=list(map(int,input().split())) l=[i for i in range(1,n+1)] for i in range(1,n+1): for j in range(2,i): if prime(j): if i%(j**m)==0: l.remove(i) else: continue print(len(l))

+ 0 comments time out!!!!!!!!!!!!!!!!!

+ 1 comment my brain hurts... and my guess is that there is a single source that solves this problem in space(s)<=500Mb and time(t)<=2s.

The approach appears to be key. Even with a fast isPrime and a fast countInclusionExclusion this ain't gonna work for 10E18 (ie 1000000000000000000000 2 [and definitely not 1])

So to my first point - [guess:] there is a single (probably simple) way to solve this problem... it will not be pretty... or it will be way obscure...

+ 0 comments My code which is passing few test cases, gives wrong answer in few test cases and times out in rest of the cases.

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner scan=new Scanner(System.in); long n=scan.nextLong(); long k=scan.nextLong(); int a=(int)Math.pow(2,k); long count=n/a; for(long i=3;Math.pow(i,k)<=n;i+=2) { if(prime(i)) { a=(int)Math.pow(i,k); count+=n/a; } } System.out.println(n-count);/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ } public static boolean prime(long n) { if(n%2==0) return false; for(int i=3;i*i<=n;i+=2) { if(n%i==0) return false; } return true; } }

Sort 26 Discussions, By:

Please Login in order to post a comment