I can't type. The correct count of primes less than a million is 78498. And there is something wrong if (nth-prime 78498) returns 100003, as the 78498th prime is 999983.<br><br><div class="gmail_quote">On Tue, Dec 11, 2012 at 10:46 AM, Martin Neal <span dir="ltr"><<a href="mailto:marty.neal@gmail.com" target="_blank">marty.neal@gmail.com</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I clicked the link, and the result shows 78498 which jives with nth-prime<div class="HOEnZb"><div class="h5"><br><br><div class="gmail_quote"> On Tue, Dec 11, 2012 at 8:31 AM, Phil Bewig <span dir="ltr"><<a href="mailto:pbewig@gmail.com" target="_blank">pbewig@gmail.com</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">There must be an error in the prime-counting function. According to <a href="<a href="http://www.wolframalpha.com/input/?i=how+many+primes+less+than+a+million" target="_blank">http://www.wolframalpha.com/input/?i=how+many+primes+less+than+a+million</a>">Wolfram|Alpha</a>, there are 79486 primes less than a million, not 78497.<div> <br></div><div>I don't use Racket, but I do have lots of Scheme code that computes with prime numbers at my <a href="<a href="http://programmingpraxis.com" target="_blank">http://programmingpraxis.com</a>>blog</a> that you may find useful.<br> <br><div class="gmail_quote"><div><div>On Tue, Dec 11, 2012 at 10:11 AM, Stephen Bloch <span dir="ltr"><<a href="mailto:sbloch@adelphi.edu" target="_blank">sbloch@adelphi.edu</a>></span> wrote:<br></div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div> <div><br> On Dec 11, 2012, at 9:03 AM, Jens Axel Søgaard wrote:<br> <br> > 2012/12/11 Stephen Bloch <<a href="mailto:bloch@adelphi.edu" target="_blank">bloch@adelphi.edu</a>>:<br> ><br> >> Would it perhaps make more sense for small-primes to contain primes<br> >> themselves, in increasing order so one can be found by binary search, rather<br> >> than booleans? The O(1) behavior would be replaced by O(log(limit)), but<br> >> perhaps you would save enough memory to put the limit higher.<br> ><br> > I think there are too many primes.<br> ><br> > Since<br> ><br> >> (require math)<br> >> (nth-prime 78498)<br> > 1000003<br> ><br> > there are 78497 primes below a million. On a 64 bit machine<br> > that requires 8*78497 = 627976 bytes.<br> <br> </div>If you treated it as a vector whose elements were (compile-time-typed) 32-bit ints, that would cut it by a factor of 2, but it would still be a third of a megabyte. OTOH, a vector of bit-packed booleans would take an eighth of a megabyte for the same limit, and give you faster lookups. So you're right; my suggestion is probably not a win.<br> <br> How many primes are below ten million? A hundred million? At some point storing the primes will take less memory than storing primality flags, but that point may be above the size of tables we can realistically store today.<br> <br> Wait: it's conceivable that there is no such crossing point. As the numbers get big, it takes O(log(limit)) bits to store numbers less than limit. The number of primes less than limit is Theta(limit/log(limit)), so storing them all takes Theta(limit) space, asymptotically the same as storing the flags.<br> <span><font color="#888888"><br> <br> <br> <br> Stephen Bloch<br> <a href="mailto:sbloch@adelphi.edu" target="_blank">sbloch@adelphi.edu</a><br> </font></span></div></div><div><div><br> <br><div> ____________________<br> Racket Users list:<br> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br> </div></div></div></blockquote></div><br></div> <br>____________________<br> Racket Users list:<br> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br> <br></blockquote></div><br> </div></div><br>____________________<br> Racket Users list:<br> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br> <br></blockquote></div><br>