The difficulty level for this challenge should be 'Advanced'.

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