On Tue, Aug 23, 2016 at 4:58 AM, Achu <ach...@gmail.com> 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? > >
