Hi together,
i would like to calculate the 10001 st prime number.
This is the code that i used, but i need to wait like hell. Any
improvement, suggestions, or ways to do it more elegantly?
{ l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));
(l;last x)] }/[{1000 >count last x};(2;enlist 2)]
Regards,
Kim
Hi, Kim!Something along those lines maybe?({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]104743 is the 10001st prime (given that 1st prime is 2)(that one was right off the bat - actually it tries all of 110000numbers,you will have to do something more intelligent to stop as soon asfound desired prime (count x))Cheers,_Oz_On Jan 14, 12:38?pm, kuentang <kuent…> wrote:> Hi together,>> i would like to calculate the 10001 st prime number.>> This is the code that i used, but i need to wait like hell. Any> improvement, suggestions, or ways to do it more elegantly?>> { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> Regards,> Kim</kuent…>
To: personal-kdbplus@googlegroups.com
X-Mailer: Apple Mail (2.1082)
http://thesweeheng.wordpress.com/2008/06/24/sieve-of-eratosthenes-in-q/
Regards,
Attila
On 14 Jan 2011, at 10:27, _Oz_ wrote:
> Hi, Kim!
>
> Something along those lines maybe?
>
> ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]
>
> 104743 is the 10001st prime (given that 1st prime is 2)
>
> (that one was right off the bat - actually it tries all of 110000
> numbers,
> you will have to do something more intelligent to stop as soon as
> found desired prime (count x))
>
> Cheers,
> _Oz_
>
> On Jan 14, 12:38 pm, kuentang <kuent…> wrote:
>> Hi together,
>>
>> i would like to calculate the 10001 st prime number.
>>
>> This is the code that i used, but i need to wait like hell. Any
>> improvement, suggestions, or ways to do it more elegantly?
>>
>> { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));
>> (l;last x)] }/[{1000 >count last x};(2;enlist 2)]
>>
>> Regards,
>> Kim
>
> –
> You received this message because you are subscribed to the Google =
Groups “Kdb+ Personal Developers” group.
> To post to this group, send email to =
personal-kdbplus@googlegroups.com.
> To unsubscribe from this group, send email to =
personal-kdbplus+unsubscribe@googlegroups.com.
> For more options, visit this group at =
http://groups.google.com/group/personal-kdbplus?hl=en.
>
</kuent…>
Hi _Oz_,thx for your solution.Your solution is much faster, because you use the sieve oferatosthenes.The implementation itself is also very straightforward.Regards,KimOn 14 Jan., 11:27, _Oz_ <zakharovo…> wrote:> Hi, Kim!>> Something along those lines maybe?>> ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]>> 104743 is the 10001st prime (given that 1st prime is 2)>> (that one was right off the bat - actually it tries all of 110000> numbers,> you will have to do something more intelligent to stop as soon as> found desired prime (count x))>> Cheers,> Oz>> On Jan 14, 12:38?pm, kuentang <kuent…> wrote:>> > Hi together,>> > i would like to calculate the 10001 st prime number.>> > This is the code that i used, but i need to wait like hell. Any> > improvement, suggestions, or ways to do it more elegantly?>> > { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> > (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> > Regards,> > Kim</kuent…></zakharovo…>
({$[min y mod x;x,y;x]}/[2;3+2*til 55000])[10000]
can save more time..
Xi
Hi _Oz_,i need to correct myself. The solution you publish is not the sieve oferatosthenes, even it works.Consider the following problem:Calculate the sum of all the primes below two million.The solution you purpose is not fast enough.On 14 Jan., 14:11, kuentang <kuent…> wrote:> Hi Oz,>> thx for your solution.>> Your solution is much faster, because you use the sieve of> eratosthenes.> The implementation itself is also very straightforward.>> Regards,> Kim>> On 14 Jan., 11:27, Oz <zakharovo…> wrote:>> > Hi, Kim!>> > Something along those lines maybe?>> > ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]>> > 104743 is the 10001st prime (given that 1st prime is 2)>> > (that one was right off the bat - actually it tries all of 110000> > numbers,> > you will have to do something more intelligent to stop as soon as> > found desired prime (count x))>> > Cheers,> > Oz>> > On Jan 14, 12:38?pm, kuentang <kuent…> wrote:>> > > Hi together,>> > > i would like to calculate the 10001 st prime number.>> > > This is the code that i used, but i need to wait like hell. Any> > > improvement, suggestions, or ways to do it more elegantly?>> > > { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> > > (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> > > Regards,> > > Kim</kuent…></zakharovo…></kuent…>
Hi, kuentang!You are absolutely right, it wasn’t the sieve.All that could be squeezed out of this easy line for the task you’vementioned will be pretty slow - around 16 min.q) \t p:{$[min y mod x@where x<=sqrt y;x,y;x]}/[(),2;3+2*til 1000000]952167q) last p1999993q) sum p1179908154Sieve should be much faster:1. it’ll reduce the scoop of candidates with each found prime < upperbound/2 (actually all that will be left after that in the scoop willbe primes)2. it will use mostly multiplication, not division.(With the sieve idea is not to test candidates, but instead reducescoop by eliminating chunks from it with each prime.)Proper implementation could be found at the link that Attila provided.But even the most naive implementation of the sieve there is (loopy,ineffective & not in functional form at all) will return the sameresult twice as fast:.a.s:3+til 2000000;.a.r:(),2;f:{.a.s:.a.s except (last .a.r)*2+til `int$((last .a.s)%last .a.r)-1;.a.r,:1#.a.s;.a.s:1_.a.s}q) \t while[(last .a.r)<(last .a.s)%2;f]472056q) p~.a.r,.a.s1bCheers,_Oz_On Jan 22, 1:51?pm, kuentang <kuent…> wrote:> Hi Oz,>> i need to correct myself. The solution you publish is not the sieve of> eratosthenes, even it works.>> Consider the following problem:>> Calculate the sum of all the primes below two million.>> The solution you purpose is not fast enough.>> On 14 Jan., 14:11, kuentang <kuent…> wrote:>>>>>>>> > Hi Oz,>> > thx for your solution.>> > Your solution is much faster, because you use the sieve of> > eratosthenes.> > The implementation itself is also very straightforward.>> > Regards,> > Kim>> > On 14 Jan., 11:27, Oz <zakharovo…> wrote:>> > > Hi, Kim!>> > > Something along those lines maybe?>> > > ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]>> > > 104743 is the 10001st prime (given that 1st prime is 2)>> > > (that one was right off the bat - actually it tries all of 110000> > > numbers,> > > you will have to do something more intelligent to stop as soon as> > > found desired prime (count x))>> > > Cheers,> > > Oz>> > > On Jan 14, 12:38?pm, kuentang <kuent…> wrote:>> > > > Hi together,>> > > > i would like to calculate the 10001 st prime number.>> > > > This is the code that i used, but i need to wait like hell. Any> > > > improvement, suggestions, or ways to do it more elegantly?>> > > > { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> > > > (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> > > > Regards,> > > > Kim</kuent…></zakharovo…></kuent…></kuent…>
Hmmm,> q) sum p> 1179908154is not the correct answer. Because of overflow the primes need to becasted to long.sum { r::long$(); {[x] f:first x; r,:long$f; :(1_x) where not0=(1_x) mod f}/[{0< count x};x]; :r} 2_til 2000000Can you provide a more elegant solution ?On 22 Jan., 15:25, _Oz_ <zakharovo…> wrote:> Hi, kuentang!>> You are absolutely right, it wasn’t the sieve.> All that could be squeezed out of this easy line for the task you’ve> mentioned will be pretty slow - around 16 min.>> q) \t p:{$[min y mod x@where x<=sqrt y;x,y;x]}/[(),2;3+2*til 1000000]> 952167>> q) last p> 1999993>> q) sum p> 1179908154>> Sieve should be much faster:> 1. it’ll reduce the scoop of candidates with each found prime < upper> bound/2 (actually all that will be left after that in the scoop will> be primes)> 2. it will use mostly multiplication, not division.> (With the sieve idea is not to test candidates, but instead reduce> scoop by eliminating chunks from it with each prime.)> Proper implementation could be found at the link that Attila provided.>> But even the most naive implementation of the sieve there is (loopy,> ineffective & not in functional form at all) will return the same> result twice as fast:> .a.s:3+til 2000000;> .a.r:(),2;> f:{.a.s:.a.s except (last .a.r)*2+til `int$((last .a.s)> %last .a.r)-1;.a.r,:1#.a.s;.a.s:1_.a.s}>> q) \t while[(last .a.r)<(last .a.s)%2;f]> 472056>> q) p~.a.r,.a.s> 1b>> Cheers,> Oz>> On Jan 22, 1:51?pm, kuentang <kuent…> wrote:>> > Hi Oz,>> > i need to correct myself. The solution you publish is not the sieve of> > eratosthenes, even it works.>> > Consider the following problem:>> > Calculate the sum of all the primes below two million.>> > The solution you purpose is not fast enough.>> > On 14 Jan., 14:11, kuentang <kuent…> wrote:>> > > Hi Oz,>> > > thx for your solution.>> > > Your solution is much faster, because you use the sieve of> > > eratosthenes.> > > The implementation itself is also very straightforward.>> > > Regards,> > > Kim>> > > On 14 Jan., 11:27, Oz <zakharovo…> wrote:>> > > > Hi, Kim!>> > > > Something along those lines maybe?>> > > > ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]>> > > > 104743 is the 10001st prime (given that 1st prime is 2)>> > > > (that one was right off the bat - actually it tries all of 110000> > > > numbers,> > > > you will have to do something more intelligent to stop as soon as> > > > found desired prime (count x))>> > > > Cheers,> > > > Oz>> > > > On Jan 14, 12:38?pm, kuentang <kuent…> wrote:>> > > > > Hi together,>> > > > > i would like to calculate the 10001 st prime number.>> > > > > This is the code that i used, but i need to wait like hell. Any> > > > > improvement, suggestions, or ways to do it more elegantly?>> > > > > { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> > > > > (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> > > > > Regards,> > > > > Kim</kuent…></zakharovo…></kuent…></kuent…></zakharovo…>
Does the solutions in Attila’s link not suit your needs?
q)p:{[s;n]$[n<4;enlist 2;r,1_where s[n]r:.z.s[s]ceiling sqrt n]}
q)s3:{@[x#010001b;y*til each ceiling x%y:2_y;:;0b]}
q)last p[s3] 2000000
1999993
q)sum `long$p[s3] 2000000
142913828984j
Regards,
Xi
Yep, sorry about it, sum long$p should do itBut anyway, it's not solution at all, just an illustration ofprinciple.For effective & elegant see http://thesweeheng.wordpress.com/2008/06/24/sieve-of-eratosthenes-in-q/That's a real masterpiece there, worthy of spending couple of days tocomprehend:s4:{x,where@[y#1b;0 1,x*til each ceiling y%x;:;0b]}pp:{[s;n]$[n\<2;0#0;()s/reverse{ceiling sqrt x}scan n]}q)\t sum long$pp[s4;2000000]98q)sum long$pp[s4;2000000]142913828922jOn Jan 22, 5:45?pm, kuentang <kuent...> wrote:> Hmmm,>> > q) sum p> > 1179908154>> is not the correct answer. Because of overflow the primes need to be> casted to long.>> sum {[x] r::long$(); { f:first x; r,:long$f; ?:(1_x) where not> 0=(1_x) mod f}/[{0< count x};x]; :r} 2_til 2000000>> Can you provide a more elegant solution ?>> On 22 Jan., 15:25, _Oz_ <zakharovo...> wrote:>>>>>>>> > Hi, kuentang!>> > You are absolutely right, it wasn't the sieve.> > All that could be squeezed out of this easy line for the task you've> > mentioned will be pretty slow - around 16 min.>> > q) \t p:{$[min y mod x@where x<=sqrt y;x,y;x]}/[(),2;3+2*til 1000000]> > 952167>> > q) last p> > 1999993>> > q) sum p> > 1179908154>> > Sieve should be much faster:> > 1. it'll reduce the scoop of candidates with each found prime < upper> > bound/2 (actually all that will be left after that in the scoop will> > be primes)> > 2. it will use mostly multiplication, not division.> > (With the sieve idea is not to test candidates, but instead reduce> > scoop by eliminating chunks from it with each prime.)> > Proper implementation could be found at the link that Attila provided.>> > But even the most naive implementation of the sieve there is (loopy,> > ineffective & not in functional form at all) will return the same> > result twice as fast:> > .a.s:3+til 2000000;> > .a.r:(),2;> > f:{.a.s:.a.s except (last .a.r)*2+til int$((last .a.s)> > %last .a.r)-1;.a.r,:1#.a.s;.a.s:1_.a.s}>> > q) \t while[(last .a.r)<(last .a.s)%2;f]> > 472056>> > q) p~.a.r,.a.s> > 1b>> > Cheers,> > Oz>> > On Jan 22, 1:51?pm, kuentang <kuent…> wrote:>> > > Hi Oz,>> > > i need to correct myself. The solution you publish is not the sieve of> > > eratosthenes, even it works.>> > > Consider the following problem:>> > > Calculate the sum of all the primes below two million.>> > > The solution you purpose is not fast enough.>> > > On 14 Jan., 14:11, kuentang <kuent…> wrote:>> > > > Hi Oz,>> > > > thx for your solution.>> > > > Your solution is much faster, because you use the sieve of> > > > eratosthenes.> > > > The implementation itself is also very straightforward.>> > > > Regards,> > > > Kim>> > > > On 14 Jan., 11:27, Oz <zakharovo…> wrote:>> > > > > Hi, Kim!>> > > > > Something along those lines maybe?>> > > > > ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]>> > > > > 104743 is the 10001st prime (given that 1st prime is 2)>> > > > > (that one was right off the bat - actually it tries all of 110000> > > > > numbers,> > > > > you will have to do something more intelligent to stop as soon as> > > > > found desired prime (count x))>> > > > > Cheers,> > > > > Oz>> > > > > On Jan 14, 12:38?pm, kuentang <kuent…> wrote:>> > > > > > Hi together,>> > > > > > i would like to calculate the 10001 st prime number.>> > > > > > This is the code that i used, but i need to wait like hell. Any> > > > > > improvement, suggestions, or ways to do it more elegantly?>> > > > > > { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> > > > > > (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> > > > > > Regards,> > > > > > Kim</kuent…></zakharovo…></kuent…></kuent…></zakharovo…></kuent…>
for s3 p should use
p:{[s;n]$[n<10;where 00110101b til n;r,1_where s[n]r:.z.s[s]ceiling sqrt n]=
}
q)sum `long$p[s3]2000000
142913828922j
Hmmm,> Does the solutions in Attila’s link not suit your needs?i somehow missed Attila’s link. The code there is really great.Regards,KimOn 22 Jan., 16:14, Xi Chen <heydic…> wrote:> Does the solutions in Attila’s link not suit your needs?>> q)p:{[s;n]$[n<4;enlist 2;r,1_where s[n]r:.z.s[s]ceiling sqrt n]}> q)s3:{@[x#010001b;y*til each ceiling x%y:2_y;:;0b]}> q)last p[s3] 2000000> 1999993> q)sum long$p[s3] 2000000> 142913828984j>> Regards,> Xi>> On 22 January 2011 14:45, kuentang <kuent...> wrote:>>>> > Hmmm,>> >> q) sum p> >> 1179908154>> > is not the correct answer. Because of overflow the primes need to be> > casted to long.>> > sum {[x] r::long$(); { f:first x; r,:long$f; ?:(1_x) where not> > 0=(1_x) mod f}/[{0< count x};x]; :r} 2_til 2000000>> > Can you provide a more elegant solution ?>> > On 22 Jan., 15:25, _Oz_ <zakharovo...> wrote:> >> Hi, kuentang!>> >> You are absolutely right, it wasn't the sieve.> >> All that could be squeezed out of this easy line for the task you've> >> mentioned will be pretty slow - around 16 min.>> >> q) \t p:{$[min y mod x@where x<=sqrt y;x,y;x]}/[(),2;3+2*til 1000000]> >> 952167>> >> q) last p> >> 1999993>> >> q) sum p> >> 1179908154>> >> Sieve should be much faster:> >> 1. it'll reduce the scoop of candidates with each found prime < upper> >> bound/2 (actually all that will be left after that in the scoop will> >> be primes)> >> 2. it will use mostly multiplication, not division.> >> (With the sieve idea is not to test candidates, but instead reduce> >> scoop by eliminating chunks from it with each prime.)> >> Proper implementation could be found at the link that Attila provided.>> >> But even the most naive implementation of the sieve there is (loopy,> >> ineffective & not in functional form at all) will return the same> >> result twice as fast:> >> .a.s:3+til 2000000;> >> .a.r:(),2;> >> f:{.a.s:.a.s except (last .a.r)*2+til int$((last .a.s)> >> %last .a.r)-1;.a.r,:1#.a.s;.a.s:1_.a.s}>> >> q) \t while[(last .a.r)<(last .a.s)%2;f]> >> 472056>> >> q) p~.a.r,.a.s> >> 1b>> >> Cheers,> >> Oz>> >> On Jan 22, 1:51?pm, kuentang <kuent…> wrote:>> >> > Hi Oz,>> >> > i need to correct myself. The solution you publish is not the sieve of> >> > eratosthenes, even it works.>> >> > Consider the following problem:>> >> > Calculate the sum of all the primes below two million.>> >> > The solution you purpose is not fast enough.>> >> > On 14 Jan., 14:11, kuentang <kuent…> wrote:>> >> > > Hi Oz,>> >> > > thx for your solution.>> >> > > Your solution is much faster, because you use the sieve of> >> > > eratosthenes.> >> > > The implementation itself is also very straightforward.>> >> > > Regards,> >> > > Kim>> >> > > On 14 Jan., 11:27, Oz <zakharovo…> wrote:>> >> > > > Hi, Kim!>> >> > > > Something along those lines maybe?>> >> > > > ({$[min y mod x;x,y;x]}/[2;3+til 110000])[10000]>> >> > > > 104743 is the 10001st prime (given that 1st prime is 2)>> >> > > > (that one was right off the bat - actually it tries all of 110000> >> > > > numbers,> >> > > > you will have to do something more intelligent to stop as soon as> >> > > > found desired prime (count x))>> >> > > > Cheers,> >> > > > Oz>> >> > > > On Jan 14, 12:38?pm, kuentang <kuent…> wrote:>> >> > > > > Hi together,>> >> > > > > i would like to calculate the 10001 st prime number.>> >> > > > > This is the code that i used, but i need to wait like hell. Any> >> > > > > improvement, suggestions, or ways to do it more elegantly?>> >> > > > > { l:1+first x; p:not 0=min l mod 2_til l ; :$[p;(l;(l,last x));> >> > > > > (l;last x)] ? }/[{1000 >count last x};(2;enlist 2)]>> >> > > > > Regards,> >> > > > > Kim>> > –> >
Submitted via Google Groups</kuent…></zakharovo…></kuent…></kuent…></zakharovo…></kuent…></heydic…>