> % time sieve 205963 > sieve.out > > That's right -- I'm finding the first 205,963 prime numbers. It runs from > around 7:00 PM EST 4 June 2008 to around 9:00 PM or 10:00 PM 5 June 2008, > when I come home from band practice, when I notice that QEMU froze probably > due to some other background processes (which is normal behavior, > unfortunately) after storing the 25,511th prime (293,681). So to get that > far, I would imagine Doug's program to be O(N^N) or O(N!). Who knows?
More likely it froze because you ran it out of memory. 25,511 primes * 1024 stack size = 25MB of memory just to hold the thread stacks. The concurrent prime sieve may be elegant, but efficient it is not. Also, I promise you that the sieve run time is less than O(N^2) if N is the maximum prime you want to get to (not the number of primes). You'd have to work pretty hard to do prime generation in O(N^N) or O(N!). > PS - I don't free channels, making sieve a memory hog as well as a CPU > cycle hog. It's a good thing you don't free channels, since they never stop being used. Russ
