Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail From: Sebastian Newsgroups: comp.lang.java.programmer Subject: Re: Java 8 Streams and Eratosthenes Date: Wed, 05 Jun 2013 09:47:55 +0200 Organization: albasani.net Lines: 26 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: news.albasani.net y74OZ2VdZ52opnTn+5GdrMsriHpss+3liEAPz/aj4B39KD772Om8xFEQUORQr3qmnWG64yawCKTGTlU6XJam9Q== NNTP-Posting-Date: Wed, 5 Jun 2013 07:47:47 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="WTeRnyesiS4zRjpYEfISF9sbsi49y3QltDFGwSCc7eeyWATZomu8KqqWCQV3K4kHtscU5dZbcyt/eSod1l3LGZTTJTWssoNgCKkl4Dtjkb1AtCI5t2j1L1m8GP0syBkr"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; de; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9 In-Reply-To: Cancel-Lock: sha1:qY9XPuXz9mqt9SyEWl5XWKJl7Fw= Xref: csiph.com comp.lang.java.programmer:24303 Am 05.06.2013 02:24, schrieb markspace: > On 6/4/2013 2:54 PM, Sebastian wrote: >> Hello there, >> >> I'd like to start an open discussion on issues involving the Streams >> API. As an exercise, I have looked at generating the first n primes, >> for some given n, using the sieve of Eratosthenes. It seemed a >> plausible enough proposition, seeing that the sieve involves repeatedly >> filtering a sequence of integers. > > > I don't think it's plausible or a good implementation. The point of this > particular sieve is that it relies on easily skipping past values and > only accessing the one's you want. For example, in an array, you can > easily compute the even numbers by adding +2 to the previous offset. > Multiples of 3 are found by adding +3 to the previous offset. Etc. > Indeed, it may be said that this particular implementation (and many others often presented as the Sieve of Eratosthenes) really isn't the sieve, but just a naive version of trial division. Cf. this paper by Melissa E. O’Neil: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf But as I said before, that wasn't really my point. -- Sebastian