You might want to check if a*a > n instead since multiplication is much cheaper than sqrt.
On Mon, Aug 22, 2016 at 5:22 PM, Taylor Pospisil <pop...@gmail.com> wrote: > 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? >> >>
