It's memory allocation. If you don't make the whole array and just break
out of the loop early you can get it about 50x faster on my machine. Also
I took the liberty of fixing a bug; you should check for <= sqrt(n).
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
if a > sqrt(n)
break
end
end
if isnprime
push!(pl,n)
ct += 1
end
n += 2
end
return pl
end
On Monday, August 22, 2016 at 4:58:30 PM UTC-4, Achu 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)]
> 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?
>
>
