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?
>>
>>

Reply via email to