# Project Euler #193: Squarefree Numbers

# Project Euler #193: Squarefree Numbers

+ 1 comment Surely there must be a mathematical trick to this. I have written my program in C++, with an efficient prime check and it still times out :(

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

+ 1 comment #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int main() { int n,p,i,j,a,t,sum,pow,res=2; cin>>n>>p; for (i=3;i<=n;i++) { a=1; for (j=2;j<=i;j++) { pow=j^p; if (i%pow==0) break; else a++; } t=0; sum=0; while (t<=i) { sum +=t; } if (sum==a) res++; } cout<<res; return 0; }

**Can someone plz help me out.The code is absolutely right but its getting timed out and also the same with my Dev C++ compiler.Feared whether my laptop may crash.**

Sort 25 Discussions, By:

Please Login in order to post a comment