Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here
(→Trial division sieves should be moved from here: clarify, add emphasis) |
|||
Line 179:
::BTW wheels can be generated, without using any trial divisions, too (e.g. [http://www.haskell.org/haskellwiki/Prime_numbers#Wheeled_list_representation this]). -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 21:18, 10 September 2014 (UTC)
: I also think they should be moved. This topic is, I believe just about moving "sieve by trial division" implementations off of this page. We have multiple possible tasks, not all of which need their own page:
: * [[Primality by trial division]]: given n, return boolean indicating whether n is prime
: * [[AKS test for primes]]: primality by extremely inefficient trial division
: * Sieve by trial division: find primes up to n using trial division (you may optimize vs. just looping over the previous task). These should not be on the SoE task, but whether they're just pushed into the [[Primality by trial division]] task or made as a separate task is a question. I believe it should be a separate task: (1) it doesn't clutter the very simple primality task, (2) it gives us a good place to put them and explain the differences, and (3) it's an interesting task for all languages, albeit not the most practical.
: * [[Sieve of Eratosthenes]]: monolithic sieve up to n
: * Sieve of Eratosthenes with wheel optimization: a proper SoE but skipping multiples of 2, 2+3, 2+3+5, etc. There are lots of examples of this on the current page. I rather like the way this is currently set up, with a simple sieve as requirement, and additional optimizations as optional. On the other hand, making it a separate task would remove clutter.
: * [[Extensible_prime_generator]]: automatically adjust size. The current task doesn't indicate how this is done, and a cursory glance shows examples using trial division, wheel trial division, M-R tests, full SoE reseives, expand by segment SoE, segment SoE iterators, segment SoA iterators, etc.
: I'd like to see a segmented sieve task (generate primes between ''a'' and ''b'' without generating all primes to ''b''), but that's a completely different topic. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 08:51, 11 September 2014 (UTC)
| |||