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.
On Tue, Dec 11, 2012 at 10:46 AM, Martin Neal <marty.n...@gmail.com> wrote: > I clicked the link, and the result shows 78498 which jives with nth-prime > > > On Tue, Dec 11, 2012 at 8:31 AM, Phil Bewig <pbe...@gmail.com> wrote: > >> There must be an error in the prime-counting function. According to <a >> href=" >> http://www.wolframalpha.com/input/?i=how+many+primes+less+than+a+million";>Wolfram|Alpha</a>, >> there are 79486 primes less than a million, not 78497. >> >> I don't use Racket, but I do have lots of Scheme code that computes with >> prime numbers at my <a href="http://programmingpraxis.com>blog</a> that >> you may find useful. >> >> On Tue, Dec 11, 2012 at 10:11 AM, Stephen Bloch <sbl...@adelphi.edu>wrote: >> >>> >>> On Dec 11, 2012, at 9:03 AM, Jens Axel Søgaard wrote: >>> >>> > 2012/12/11 Stephen Bloch <bl...@adelphi.edu>: >>> > >>> >> Would it perhaps make more sense for small-primes to contain primes >>> >> themselves, in increasing order so one can be found by binary search, >>> rather >>> >> than booleans? The O(1) behavior would be replaced by O(log(limit)), >>> but >>> >> perhaps you would save enough memory to put the limit higher. >>> > >>> > I think there are too many primes. >>> > >>> > Since >>> > >>> >> (require math) >>> >> (nth-prime 78498) >>> > 1000003 >>> > >>> > there are 78497 primes below a million. On a 64 bit machine >>> > that requires 8*78497 = 627976 bytes. >>> >>> 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. >>> >>> 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. >>> >>> 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. >>> >>> >>> >>> >>> Stephen Bloch >>> sbl...@adelphi.edu >>> >>> >>> ____________________ >>> Racket Users list: >>> http://lists.racket-lang.org/users >>> >> >> >> ____________________ >> Racket Users list: >> http://lists.racket-lang.org/users >> >> > > ____________________ > Racket Users list: > http://lists.racket-lang.org/users > >
____________________ Racket Users list: http://lists.racket-lang.org/users
