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...

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))

time out!!!!!!!!!!!!!!!!!

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...

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;
    }
}