I see. Thanks!
On Monday, 22 August 2016 18:28:15 UTC-5, Yichao Yu wrote: > > > > On Tue, Aug 23, 2016 at 4:58 AM, Achu <ach...@gmail.com <javascript:>> > wrote: > >> I have a simple piece of code that finds me 10001 prime numbers. >> >> function a() >> pl=[2] >> n=3 >> ct=1 >> while(ct<10001) >> isnprime=true >> for a in pl >> if n%a==0 >> isnprime=false >> break >> end >> end >> if isnprime >> push!(pl,n) >> ct+=1 >> end >> n+=2 >> end >> return pl >> end >> >> When I tweaked the code to check only prime factors less than the sqrt of >> the number, it slowed it down by a factor of 3. >> >> function a() >> pl=[2] >> n=3 >> ct=1 >> while(ct<10001) >> isnprime=true >> for a in pl[pl.<sqrt(n)] >> > > Loops are as fast as "vectorized" (in MATLAB sense) array operations so > this won't give you any speed improvement at all. > > The loop was operating on all the elements (O(n)) and the check you add is > also O(n) with possibly a larger constant factor since it allocates > multiple arrays > > Simply do > > if a >= sqrt(n) > break > end > > should work > > >> if n%a==0 >> isnprime=false >> break >> end >> end >> if isnprime >> push!(pl,n) >> ct+=1 >> end >> n+=2 >> end >> return pl >> end >> >> Why is that? >> >> >
