We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #193: Squarefree Numbers
  4. Discussions

Project Euler #193: Squarefree Numbers

  • vjvjain0
     + 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;
    }
}