Sieve of Eratosthenes: Difference between revisions

*   [[sequence of primes by Trial Division]]

<br><br>

 

=={{header|360 Assembly}}==

For maximum compatibility, this program uses only the basic instruction set.

ERATOST CSECT

USING ERATOST,R12

CRIBLE DC 100000X'01'

YREGS

{{out}}

<pre style="height:20ex">

=={{header|6502 Assembly}}==

If this subroutine is called with the value of <i>n</i> in the accumulator, it will store an array of the primes less than <i>n</i> beginning at address 1000 hex and return the number of primes it has found in the accumulator.

LDA #$00

LDX #$00

JMP COPY

COPIED: TYA ; how many found

 

=={{header|68000 Assembly}}==

Some of the macro code is derived from the examples included with EASy68K.

See 68000 "100 Doors" listing for additional information.

* Title : BitSieve

* Written by : G. A. Tippery

Summary2: DC.B ' prime numbers found.',CR,LF,$00

 

 

=={{header|ABAP}}==

PARAMETERS: p_limit TYPE i OBLIGATORY DEFAULT 100.

 

ENDIF.

ENDLOOP.

=={{header|ACL2}}==

(declare (xargs :measure (nfix (- n i))))

(if (zp (- n i))

 

(defun sieve (limit)

 

=={{header|ActionScript}}==

Works with ActionScript 3.0 (this is utilizing the actions panel, not a separated class file)

{

var primes:Array = new Array();

}

var e:Array = eratosthenes(1000);

Output:

{{out}}

=={{header|Ada}}==

 

 

procedure Eratos is

Last: Positive := Positive'Value(Ada.Command_Line.Argument(1));

Prime: array(1 .. Last) of Boolean := (1 => False, others => True);

Cnt: Positive;

begin

if Prime(Base) then

Cnt := Base + Base;

Prime(Cnt) := False;

Cnt := Cnt + Base;

end if;

end loop;

 

{{out}}

=={{header|Agda}}==

 

-- imports

open import Data.Nat as ℕ using (ℕ; suc; zero; _+_; _∸_)

remove _ ys zero = nothing ∷ ys i

remove y ys (suc j) = y ∷ ys j

 

=={{header|Agena}}==

Tested with Agena 2.9.5 Win32

 

# generate and return a sequence containing the primes up to sieveSize

 

# test the sieve proc

{{out}}

<pre>

 

'''Works with:''' ALGOL 60 for OS/360

'INTEGER' 'ARRAY' CANDIDATES(/0..1000/);

'INTEGER' I,J,K;

'END'

'END'

 

=={{header|ALGOL 68}}==

PROC eratosthenes = (INT n)[]BOOL:

(

);

{{out}}

<pre>

FTTFTFTFFFTFTFFFTFTFFFTFFFFFTFTFFFFFTFFFTFTFFFTFFFFFTFFFFFTFTFFFFFTFFFTFTFFFFFTF

</pre>

 

=={{header|ALGOL-M}}==

BEGIN

 

COMMENT

FIND PRIMES UP TO THE SPECIFIED LIMIT (HERE 1,000) USING

 

% CALCULATE INTEGER SQUARE ROOT %

 

% INITIALIZE TABLE %

FOR I := 1 STEP 1 UNTIL LIMIT DO

FLAGS[I] := TRUE;

 

% SIEVE FOR PRIMES %

FOR I := 2 STEP 1 UNTIL ISQRT(LIMIT) DO

BEGIN

END;

 

COUNT := 0;

COL := 1;

FOR I := 2 STEP 1 UNTIL LIMIT DO

BEGIN

COUNT := COUNT + 1;

COL := COL + 1;

BEGIN

COL := 1;

END;

END;

 

 

END

{{out}}

<pre>

</pre>

 

 

All these versions requires<tt> ⎕io←0 </tt>(index origin 0).

=== Non-Optimized Version ===

 

b←⍵⍴1

b[⍳2⌊⍵]←0

}

 

 

The required list of prime divisors obtains by recursion (<tt>{⍵/⍳⍴⍵}∇⌈⍵*0.5</tt>).

 

 

b←⍵⍴{∧⌿↑(×/⍵)⍴¨~⍵↑¨1}2 3 5

b[⍳6⌊⍵]←(6⌊⍵)⍴0 0 1 1 0 1

}

 

 

The optimizations are as follows:

=== Examples ===

 

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 

 

+/∘sieve¨ 10*⍳10

 

The last expression computes the number of primes < 1e0 1e1 ... 1e9.

The last number 50847534 can perhaps be called the anti-Bertelsen's number (http://mathworld.wolfram.com/BertelsensNumber.html).

 

 

 

 

 

<pre>

</pre>

 

{{AutoHotkey case}}Source: [http://www.autohotkey.com/forum/topic44657.html AutoHotkey forum] by Laszlo

 

Sieve(n) { ; Sieve of Eratosthenes => string of 0|1 chars, 1 at position k: k is prime

}

Return S

$M = InputBox("Integer", "Enter biggest Integer")

Global $a[$M], $r[$M], $c = 1

$r[0] = $c - 1

ReDim $r[$c]

 

=={{header|AWK}}==

input from commandline as well as stdin,

and input is checked for valid numbers:

# usage: gawk -v n=101 -f sieve.awk

 

 

END { print "Bye!" }

 

Here is an alternate version that uses an associative array to record composites with a prime dividing it. It can be considered a slow version, as it does not cross out composites until needed. This version assumes enough memory to hold all primes up to ULIMIT. It prints out noncomposites greater than 1.

BEGIN { ULIMIT=100

 

else print ( S[(n+n)] = n )

}

 

==Bash==

{{works with|FreeBASIC}}

{{works with|RapidQ}}

 

INPUT "Enter number to search to: "; limit

FOR n = 2 TO limit

IF flags(n) = 0 THEN PRINT n; ", ";

 

==={{header|Applesoft BASIC}}===

20 DIM FLAGS(LIMIT)

30 FOR N = 2 TO SQR (LIMIT)

100 FOR N = 2 TO LIMIT

110 IF FLAGS(N) = 0 THEN PRINT N;", ";

 

==={{header|IS-BASIC}}===

110 LET LIMIT=100

120 NUMERIC T(1 TO LIMIT)

230 FOR I=2 TO LIMIT ! Display the primes

240 IF T(I)=0 THEN PRINT I;

 

==={{header|Locomotive Basic}}===

20 INPUT "Limit";limit

30 DIM f(limit)

100 FOR n=2 TO limit

110 IF f(n)=0 THEN PRINT n;",";

 

==={{header|MSX Basic}}===

60 LET p(k)=1

70 NEXT k

80 NEXT n

 

==={{header|Sinclair ZX81 BASIC}}===

 

A note on <code>FAST</code> and <code>SLOW</code>: under normal circumstances the CPU spends about 3/4 of its time driving the display and only 1/4 doing everything else. Entering <code>FAST</code> mode blanks the screen (which we do not want to update anyway), resulting in substantially improved performance; we then return to <code>SLOW</code> mode when we have something to print out.

20 FAST

30 DIM N(L)

110 FOR I=2 TO L

120 IF NOT N(I) THEN PRINT I;" ";

 

==={{header|ZX Spectrum Basic}}===

20 DIM p(l)

30 FOR n=2 TO SQR l

100 FOR n=2 TO l

110 IF p(n)=0 THEN PRINT n;", ";

 

 

=={{header|Batch File}}==

@echo off

setlocal ENABLEDELAYEDEXPANSION

if !crible.%%i! EQU 1 echo %%i

)

{{Out}}

<pre style="height:20ex">limit: 100

89

97</pre>

 

=={{header|Befunge}}==

@ ^ p3\" ":<

2 234567890123456789012345678901234567890123456789012345678901234567890123456789

 

=={{header|Bracmat}}==

This solution does not use an array. Instead, numbers themselves are used as variables. The numbers that are not prime are set (to the silly value "nonprime"). Finally all numbers up to the limit are tested for being initialised. The uninitialised (unset) ones must be the primes.

= n j i

. !arg:?n

)

& eratosthenes$100

{{out}}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 

=={{header|C}}==

#include <math.h>

 

}

return sieve;

 

'''Another example:'''

Then, in a loop, fill zeroes into those places where i * j is less than or equal to n (number of primes requested), which means they have multiples!

To understand this better, look at the output of the following example.

#include <malloc.h>

void sieve(int *, int);

}

printf("\n\n");

j:2

Before a[2*2]: 1

i:9

i:10

 

=={{header|C sharp|C#}}==

{{works with|C sharp|C#|2.0+}}

using System.Collections;

using System.Collections.Generic;

}

}

 

 

{{trans|F#}}

 

To show that C# code can be written in somewhat functional paradigms, the following in an implementation of the Richard Bird sieve from the Epilogue of [Melissa E. O'Neill's definitive article](http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) in Haskell:

using System.Collections;

using System.Collections.Generic;

}

IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); }

 

 

{{trans|F#}}

 

The above code can easily be converted to "'''odds-only'''" and a infinite tree-like folding scheme with the following minor changes:

using System.Collections;

using System.Collections.Generic;

}

IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); }

 

The above code runs over ten times faster than the original Richard Bird algorithm.

 

 

{{trans|F#}}

 

First, an implementation of a Min Heap Priority Queue is provided as extracted from the entry at [http://rosettacode.org/wiki/Priority_queue#C.23 RosettaCode], with only the necessary methods duplicated here:

using KeyT = System.UInt32;

using System;

public static MinHeapPQ<V> replaceMin(KeyT k, V v, MinHeapPQ<V> pq) {

pq.rplcmin(k, v); return pq; }

 

The following code implements an improved version of the '''odds-only''' O'Neil algorithm, which provides the improvements of only adding base prime composite number streams to the queue when the sieved number reaches the square of the base prime (saving a huge amount of memory and considerable execution time, including not needing as wide a range of a type for the internal prime numbers) as well as minimizing stream processing using fusion:

using System.Collections;

using System.Collections.Generic;

public IEnumerator<PrimeT> GetEnumerator() { return nmrtr(); }

IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); }

 

The above code is at least about 2.5 times faster than the Tree Folding version.

 

 

The above code adds quite a bit of overhead in having to provide a version of a Priority Queue for little advantage over a Dictionary (hash table based) version as per the code below:

using System.Collections;

using System.Collections.Generic;

public IEnumerator<PrimeT> GetEnumerator() { return nmrtr(); }

IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); }

 

The above code runs in about three quarters of the time as the above Priority Queue based version for a range of a million primes which will fall even further behind for increasing ranges due to the Dictionary providing O(1) access times as compared to the O(log n) access times for the Priority Queue; the only slight advantage of the PQ based version is at very small ranges where the constant factor overhead of computing the table hashes becomes greater than the "log n" factor for small "n".

 

 

All of the above unbounded versions are really just an intellectual exercise as with very little extra lines of code above the fastest Dictionary based version, one can have an bit-packed page-segmented array based version as follows:

using System.Collections;

using System.Collections.Generic;

public IEnumerator<PrimeT> GetEnumerator() { return nmrtr(); }

IEnumerator IEnumerable.GetEnumerator() { return (IEnumerator)GetEnumerator(); }

 

The above code is about 25 times faster than the Dictionary version at computing the first about 50 million primes (up to a range of one billion), with the actual enumeration of the result sequence now taking longer than the time it takes to cull the composite number representation bits from the arrays, meaning that it is over 50 times faster at actually sieving the primes. The code owes its speed as compared to a naive "one huge memory array" algorithm to using an array size that is the size of the CPU L1 or L2 caches and using bit-packing to fit more number representations into this limited capacity; in this way RAM memory access times are reduced by a factor of from about four to about 10 (depending on CPU and RAM speed) as compared to those naive implementations, and the minor computational cost of the bit manipulations is compensated by a large factor in total execution time.

 

 

In order to make further gains in speed, custom methods must be used to avoid using iterator sequences. If this is done, then further gains can be made by extreme wheel factorization (up to about another about four times gain in speed) and multi-processing (with another gain in speed proportional to the actual independent CPU cores used).

 

All of the above unbounded code can be tested by the following "main" method (replace the name "PrimesXXX" with the name of the class to be tested):

 

To produce the following output for all tested versions (although some are considerably faster than others):

{{output}}

<pre>15485863</pre>

 

=={{header|Chapel}}==

This solution uses nested iterators to create new wheels at run time:

iter sieve(prime):int {

 

 

// candidate is a multiple of this prime

// remember size of last composite

last = composite;

yield candidate;

}

for p in sieve(2) {

writeln();

break;

}

 

=={{header|Clojure}}==

 

 

"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"

[n]

(do (dorun (map #(cullp %) (filter #(not (aget cmpsts %))

(range 2 (inc root)))))

 

'''Alternative implementation using Clojure's side-effect oriented list comprehension.'''

 

"Returns a lazy sequence of prime numbers less than lim"

[lim]

(doseq [j (range (* i i) lim i)]

(aset refs j false)))

 

'''Alternative implementation using Clojure's side-effect oriented list comprehension. Odds only.'''

"Returns a lazy sequence of prime numbers less than lim"

[lim]

(doseq [j (range (* (+ i i) (inc i)) max-i (+ i i 1))]

(aset refs j false)))

the multiples of primes to mark as composite is also (2*i + 1).

The index of the square of the prime to start composite marking is 2*i*(i+1).

'''Alternative very slow entirely functional implementation using lazy sequences'''

 

"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"

[n]

(cons p (lazy-seq (nxtprm (-> (range (* p p) (inc n) p)

set (remove cs) rest)))))))]

 

The reason that the above code is so slow is that it has has a high constant factor overhead due to using a (hash) set to remove the composites from the future composites stream, each prime composite stream removal requires a scan across all remaining composites (compared to using an array or vector where only the culled values are referenced, and due to the slowness of Clojure sequence operations as compared to iterator/sequence operations in other languages.

 

Here is an immutable boolean vector based non-lazy sequence version other than for the lazy sequence operations to output the result:

"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"

[max-prime]

(assoc 1 false)

(sieve 2))

 

The above code is still quite slow due to the cost of the immutable copy-on-modify operations.

 

The following code implements an odds-only sieve using a mutable bit packed long array, only using a lazy sequence for the output of the resulting primes:

 

(defn primes-to

(recur (inc i)))))))))]

(if (< n 2) nil

 

The above code is about as fast as any "one large sieving array" type of program in any computer language with this level of wheel factorization other than the lazy sequence operations are quite slow: it takes about ten times as long to enumerate the results as it does to do the actual sieving work of culling the composites from the sieving buffer array. The slowness of sequence operations is due to nested function calls, but primarily due to the way Clojure implements closures by "boxing" all arguments (and perhaps return values) as objects in the heap space, which then need to be "un-boxed" as primitives as necessary for integer operations. Some of the facilities provided by lazy sequences are not needed for this algorithm, such as the automatic memoization which means that each element of the sequence is calculated only once; it is not necessary for the sequence values to be retraced for this algorithm.

 

The following code overcomes many of those limitations by using an internal (OPSeq) "deftype" which implements the ISeq interface as well as the Counted interface to provide immediate count returns (based on a pre-computed total), as well as the IReduce interface which can greatly speed come computations based on the primes sequence (eased greatly using facilities provided by Clojure 1.7.0 and up):

"Computes lazy sequence of prime numbers up to a given number using sieve of Eratosthenes"

[n]

(toString [this] (if (= cnt tcnt) "()"

(.toString (seq (map identity this))))))

 

'(time (count (primes-tox 10000000)))' takes about 40 milliseconds (compiled) to produce 664579.

 

'''A Clojure version of Richard Bird's Sieve using Lazy Sequences (sieves odds only)'''

"Computes the unbounded sequence of primes using a Sieve of Eratosthenes algorithm by Richard Bird."

[]

(do (def oddprms (cons 3 (lazy-seq (let [cmpsts (-> oddprms (allmtpls) (mrgmltpls))]

(minusStrtAt 5 cmpsts)))))

 

The above code is quite slow due to both that the data structure is a linear merging of prime multiples and due to the slowness of the Clojure sequence operations.

 

The following code speeds up the above code by merging the linear sequence of sequences as above by pairs into a right-leaning tree structure:

"Computes the unbounded sequence of primes using a Sieve of Eratosthenes algorithm modified from Bird."

[]

(do (def oddprms (cons 3 (lazy-seq (let [cmpsts (-> oddprms (allmtpls) (mrgmltpls))]

(minusStrtAt 5 cmpsts)))))

 

The above code is still slower than it should be due to the slowness of Clojure's sequence operations.

 

The following code uses a custom "deftype" non-memoizing Co Inductive Stream/Sequence (CIS) implementing the ISeq interface to make the sequence operations more efficient and is about four times faster than the above code:

clojure.lang.ISeq

(first [_] v)

(do (def oddprms (->CIS 3 (fn [] (let [cmpsts (-> oddprms (allmtpls) (mrgmltpls))]

(minusStrtAt 5 cmpsts)))))

 

'(time (count (take-while #(<= (long %) 10000000) (primes-treeFoldingx))))' takes about 3.4 seconds for a range of 10 million.

 

The following code is a version of the O'Neill Haskell code but does not use wheel factorization other than for sieving odds only (although it could be easily added) and uses a Hash Map (constant amortized access time) rather than a Priority Queue (log n access time for combined remove-and-insert-anew operations, which are the majority used for this algorithm) with a lazy sequence for output of the resulting primes; the code has the added feature that it uses a secondary base primes sequence generator and only adds prime culling sequences to the composites map when they are necessary, thus saving time and limiting storage to only that required for the map entries for primes up to the square root of the currently sieved number:

"Infinite sequence of primes using an incremental Sieve or Eratosthenes with a Hashmap"

[]

(cons c (lazy-seq (nxtoddprm (+ c 2) q bsprms cmpsts))))))]

(do (def baseoddprms (cons 3 (lazy-seq (nxtoddprm 5 9 baseoddprms {}))))

 

The above code is slower than the best tree folding version due to the added constant factor overhead of computing the hash functions for every hash map operation even though it has computational complexity of (n log log n) rather than the worse (n log n log log n) for the previous incremental tree folding sieve. It is still about 100 times slower than the sieve based on the bit-packed mutable array due to these constant factor hashing overheads.

 

In order to implement the O'Neill Priority Queue incremental Sieve of Eratosthenes algorithm, one requires an efficient implementation of a Priority Queue, which is not part of standard Clojure. For this purpose, the most suitable Priority Queue is a binary tree heap based MinHeap algorithm. The following code implements a purely functional (using entirely immutable state) MinHeap Priority Queue providing the required functions of (emtpy-pq) initialization, (getMin-pq pq) to examinte the minimum key/value pair in the queue, (insert-pq pq k v) to add entries to the queue, and (replaceMinAs-pq pq k v) to replaace the minimum entry with a key/value pair as given (it is more efficient that if functions were provided to delete and then re-insert entries in the queue; there is therefore no "delete" or other queue functions supplied as the algorithm does not requrie them:

Object

(toString [_] (str "<" k "," v ">")))

(if (<= kl kr)

(recur l #(cont (->PQNode kvl % r)))

 

Note that the above code is written partially using continuation passing style so as to leave the "recur" calls in tail call position as required for efficient looping in Clojure; for practical sieving ranges, the algorithm could likely use just raw function recursion as recursion depth is unlikely to be used beyond a depth of about ten or so, but raw recursion is said to be less code efficient.

 

The actual incremental sieve using the Priority Queue is as follows, which code uses the same optimizations of postponing the addition of prime composite streams to the queue until the square root of the currently sieved number is reached and using a secondary base primes stream to generate the primes composite stream markers in the queue as was used for the Hash Map version:

"Infinite sequence of primes using an incremental Sieve or Eratosthenes with a Priority Queue"

[]

(cons c (lazy-seq (nxtoddprm (+ c 2) q bsprms cmpsts)))))))]

(do (def baseoddprms (cons 3 (lazy-seq (nxtoddprm 5 9 baseoddprms (empty-pq)))))

 

The above code is faster than the Hash Map version up to about a sieving range of fifteen million or so, but gets progressively slower for larger ranges due to having (n log n log log n) computational complexity rather than the (n log log n) for the Hash Map version, which has a higher constant factor overhead that is overtaken by the extra "log n" factor.

To show that Clojure does not need to be particularly slow, the following version runs about twice as fast as the non-segmented unbounded array based version above (extremely fast compared to the non-array based versions) and only a little slower than other equivalent versions running on virtual machines: C# or F# on DotNet or Java and Scala on the JVM:

 

 

(def PGSZ (bit-shift-left 1 14)) ;; size of CPU cache

(next pgseq)

(+ cnt (count-pg PGBTS pg))))))]

 

The above code runs just as fast as other virtual machine languages when run on a 64-bit JVM; however, when run on a 32-bit JVM it runs almost five times slower. This is likely due to Clojure only using 64-bit integers for integer operations and these operations getting JIT compiled to use library functions to simulate those operations using combined 32-bit operations under a 32-bit JVM whereas direct CPU operations can be used on a 64-bit JVM

 

The base primes culling page size is reduced from the page size for the main primes so that there is less overhead for smaller primes ranges; otherwise excess base primes are generated for fairly small sieve ranges.

 

=={{header|CMake}}==

# Check for integer overflow. With CMake using 32-bit signed integer,

# this check fails when limit > 46340.

endforeach(i)

set(${var} ${list} PARENT_SCOPE)

# Print all prime numbers through 100.

eratosthenes(primes 100)

 

=={{header|COBOL}}==

*> which are kludges to get syntax highlighting to work.

IDENTIFICATION DIVISION.

 

GOBACK

 

=={{header|Common Lisp}}==

(loop

with sieve = (make-array (1+ maximum)

and do (loop for composite from (expt candidate 2)

to maximum by candidate

 

Working with odds only (above twice speedup), and marking composites only for primes up to the square root of the maximum:

 

"Prime numbers sieve for odd numbers.

Returns a list with all the primes that are less than or equal to maximum."

:do (loop :for j :from (* i (1+ i) 2) :to maxi :by odd-number

:do (setf (sbit sieve j) 1))

 

The indexation scheme used here interprets each index <code>i</code> as standing for the value <code>2i+1</code>. Bit <code>0</code> is unused, a small price to pay for the simpler index calculations compared with the <code>2i+3</code> indexation scheme. The multiples of a given odd prime <code>p</code> are enumerated in increments of <code>2p</code>, which corresponds to the index increment of <code>p</code> on the sieve array. The starting point <code>p*p = (2i+1)(2i+1) = 4i(i+1)+1</code> corresponds to the index <code>2i(i+1)</code>.

 

While formally a ''wheel'', odds are uniformly spaced and do not require any special processing except for value translation. Wheels proper aren't uniformly spaced and are thus trickier.

 

=={{header|D}}==

===Simpler Version===

 

uint[] sieve(in uint limit) nothrow @safe {

void main() {

50.sieve.writeln;

{{out}}

<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]</pre>

===Faster Version===

This version uses an array of bits (instead of booleans, that are represented with one byte), and skips even numbers. The output is the same.

 

size_t[] sieve(in size_t m) pure nothrow @safe {

void main() {

50.sieve.writeln;

 

===Extensible Version===

(This version is used in the task [[Extensible prime generator#D|Extensible prime generator]].)

struct Prime {

uint[] a = [2];

uint.max.iota.map!prime.until!q{a > 50}.writeln;

}

To see the output (that is the same), compile with <code>-version=sieve_of_eratosthenes3_main</code>.

 

=={{header|Dart}}==

String iterableToString(Iterable seq) {

String str = "[";

print(iterableToString(sortedValues)); // expect sieve.length to be 168 up to 1000...

// Expect.equals(168, sieve.length);

{{out}}<pre>

Found 168 primes up to 1000 in 9 milliseconds.

 

===faster bit-packed array odds-only solution===

import 'dart:math';

 

print("There were $answer primes found up to $range.");

print("This test bench took $elapsed milliseconds.");

{{output}}

<pre>( 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 )

The following code will have about O(n log (log n)) performance due to a hash table having O(1) average performance and is only somewhat slow due to the constant overhead of processing hashes:

 

Iterable<int> oddprms() sync* {

yield(3); yield(5); // need at least 2 for initialization

print("There were $answer primes found up to $range.");

print("This test bench took $elapsed milliseconds.");

{{output}}

<pre>( 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 )

 

{{trans|Kotlin}}

import 'dart:math';

import 'dart:collection';

print("There were $answer primes found up to $range.");

print("This test bench took $elapsed milliseconds.");

{{output}}

<pre>( 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 )

 

The algorithm can be sped up by a factor of four by extreme wheel factorization and (likely) about a factor of the effective number of CPU cores by using multi-processing isolates, but there isn't much point if one is to use the prime generator for output. For most purposes, it is better to use custom functions that directly manipulate the culled bit-packed page segments as `countPrimesTo` does here.

 

=={{header|Delphi}}==

 

{$APPTYPE CONSOLE}

Sieve.Free;

readln;

Output:

<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 </pre>

 

 

=={{header|DWScript}}==

 

var

n, k : Integer;

var i : Integer;

for i:=0 to r.High do

 

=={{header|Dylan}}==

With outer to sqrt and inner to p^2 optimizations:

let limit = floor(n ^ 0.5) + 1;

let sieve = make(limited(<simple-vector>, of: <boolean>), size: n + 1, fill: #t);

if (sieve[x]) format-out("Prime: %d\n", x); end;

end;

 

=={{header|E}}==

 

=={{header|EasyLang}}==

.

 

=={{header|eC}}==

{{incorrect|eC|It uses rem testing and so is a trial division algorithm, not a sieve of Eratosthenes.}}

Note: this is not a Sieve of Eratosthenes; it is just trial division.

public class FindPrime

{

}

}

=={{header|EchoLisp}}==

===Sieve===

 

;; converts sieve->list for integers in [nmin .. nmax[

→ (1000003 1000033 1000037 1000039 1000081 1000099)

(s-next-prime s-primes 9_000_000)

 

===Segmented sieve===

Allow to extend the basis sieve (n) up to n^2. Memory requirement is O(√n)

;; delta multiple of sqrt(n)

;; segment is [left .. left+delta-1]

 

;; 8 msec using the native (prime?) function

 

===Wheel===

A 2x3 wheel gives a 50% performance gain.

(define (weratosthenes n)

(define primes (make-bit-vector n )) ;; everybody to #f (false)

(for ([j (in-range (* p p) n p)])

(bit-vector-set! primes j #f)))