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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #193: Squarefree Numbers
  4. Discussions

Project Euler #193: Squarefree Numbers

Problem
Submissions
Leaderboard
Discussions

Sort 26 Discussions, By:

recency

Please Login in order to post a comment

  • byhill
    4 weeks ago+ 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|
    Permalink
  • baythapudisaikr1
    2 years ago+ 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|
    Permalink
  • aman2000jaiswal1
    4 years ago+ 0 comments

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

    0|
    Permalink
  • nick_thurn
    5 years ago+ 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|
    Permalink
  • vjvjain0
    5 years ago+ 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;
        }
    }
    
    -2|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy