Sieve of Eratosthenes: Difference between revisions

{{trans|Python}}

V is_prime = [0B]*2 [+] [1B]*(limit - 1)

L(n) 0 .< Int(limit ^ 0.5 + 1.5)

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

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

ERATOST CSECT

USING ERATOST,R12

=={{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

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

=={{header|8086 Assembly}}==

cpu 8086

bits 16

=={{header|8th}}==

with: n

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program cribleEras64.s */

=={{header|ABAP}}==

PARAMETERS: p_limit TYPE i OBLIGATORY DEFAULT 100.

=={{header|ACL2}}==

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

(if (zp (- n i))

=={{header|Action!}}==

PROC Main()

=={{header|ActionScript}}==

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

{

var primes:Array = new Array();

=={{header|Ada}}==

procedure Eratos is

=={{header|Agda}}==

-- imports

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

=={{header|Agena}}==

Tested with Agena 2.9.5 Win32

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

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

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

'INTEGER' I,J,K;

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

PROC eratosthenes = (INT n)[]BOOL:

(

=={{header|ALGOL W}}==

=== Standard, non-optimised sieve ===

% implements the sieve of Eratosthenes %

Alternative version that only stores odd numbers greater than 1 in the sieve.

% implements the sieve of Eratosthenes %

% only odd numbers appear in the sieve, which starts at 3 %

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

BEGIN

=== Non-Optimized Version ===

b←⍵⍴1

b[⍳2⌊⍵]←0

=== Optimized Version ===

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

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

=== 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

=={{header|AppleScript}}==

script o

property numberList : {missing value}

{{out}}

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

=={{header|Arturo}}==

composites: array.of: inc upto false

loop 2..to :integer sqrt upto 'x [

=={{header|AutoHotkey}}==

{{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

===Alternative Version===

arr := []

loop % n-1

return Arr

}</syntaxhighlight>

Arr := Sieve_of_Eratosthenes(n)

loop, % n-1

=={{header|AutoIt}}==

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

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

input from commandline as well as stdin,

and input is checked for valid numbers:

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

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

{{works with|FreeBASIC}}

{{works with|RapidQ}}

INPUT "Enter number to search to: "; limit

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

20 DIM FLAGS(LIMIT)

30 FOR N = 2 TO SQR (LIMIT)

{{trans|Commodore BASIC}}

Auto-initialization of arrays is not reliable, so we have to do our own. Also, PRINTing with commas doesn't quite format as nicely as one might hope, so we do a little extra work to keep the columns lined up.

110 PRINT "LIMIT";:INPUT LI

120 DIM N(LI):FOR I=0 TO LI:N(I)=1:NEXT I

==={{header|Commodore BASIC}}===

Since C= BASIC initializes arrays to all zeroes automatically, we avoid needing our own initialization loop by simply letting 0 mean prime and using 1 for composite.

110 INPUT "LIMIT";LI

120 DIM N(LI)

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

110 LET LIMIT=100

120 NUMERIC T(1 TO LIMIT)

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

20 INPUT "Limit";limit

30 DIM f(limit)

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

6 REM Translated from Rosetta's ZX Spectrum implementation

10 INPUT "Enter number to search to: ";l

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)

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

20 DIM p(l)

30 FOR n=2 TO SQR l

{{works with|QBasic|1.1}}

{{works with|QuickBasic|4.5}}

DIM flags(limit)

==={{header|BASIC256}}===

limit = 120

==={{header|True BASIC}}===

{{trans|QBasic}}

DIM flags(0)

MAT redim flags(limit)

{{trans|ZX Spectrum Basic}}

Sets h$ to 1 for higher multiples of 2 via <code>FILL$</code>, later on sets <code>STEP</code> to 2n; replaces Floating Pt array p(z) with string variable h$(z) to sieve out all primes < z=441 (<code>l</code>=21) in under 1K, so that h$ is fillable to its maximum (32766), even on a 48K ZX Spectrum if translated back.

10 INPUT "Enter Stopping Pt for squared factors: ";z

15 LET l=SQR(z)

====2i wheel emulation of Sinclair ZX81 BASIC====

10 INPUT Z

15 LET L=SQR(Z)

====2i wheel emulation of Sinclair ZX80 BASIC====

. . . with 2:1 compression (of 16-bit integer variables on ZX80s) such that it obviates having to account for any multiple of 2; one has to input odd upper limits on factors to be squared, <code>L</code> (=21 at most on 1K ZX80s for all primes till 439).

10 INPUT L

15 LET Z=(L+1)*(L- 1)/2

duplicate entries are omitted. Thus, a slightly transformed Sieve of Sundaram is what Eratosthenes' Sieve becomes upon applying all

optimisations incorporated into the prior entries for QL SuperBASIC, except for any equivalent to line 50 in them.

10 INPUT O

15 LET Z=2*O*O+O*2

====Eulerian optimisation====

While slower than the optimised Sieve of Eratosthenes before it, the Sieve of Sundaram above has a compatible compression scheme that's more convenient than the conventional one used beforehand. It is therefore applied below along with Euler's alternative optimisation in a reversed implementation that lacks backward-compatibility to ZX80 BASIC. This program is designed around features & limitations of the QL, yet can be rewritten more efficiently for 1K ZX80s, as they allow integer variables to be parameters of <code>FOR</code> statements (& as their 1K of static RAM is equivalent to L1 cache, even in <code>FAST</code> mode). That's left as an exercise for ZX80 enthusiasts, who for o%=14 should be able to generate all primes < 841, i.e. 3 orders of (base 2) magnitude above the limit for the program listed under Sinclair ZX81 BASIC. In QL SuperBASIC, o% may at most be 127--generating all primes < 65,025 (almost 2x the upper limit for indices & integer variables used to calculate them ~2x faster than for floating point as used in line 30, after which the integer code mimics an assembly algorithm for the QL's 68008.)

10 INPUT "Enter highest value of diagonal index q%: ";o%

15 LET z%=o%*(2+o%*2) : h$=FILL$(" ",z%+o%) : q%=1 : q=q% : m=z% DIV (2*q%+1)

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

@echo off

setlocal ENABLEDELAYEDEXPANSION

=={{header|BBC BASIC}}==

DIM sieve% limit%

=={{header|BCPL}}==

manifest $( LIMIT = 1000 $)

=== Odds-only bit packed array version (64 bit) ===

This sieve also uses an iterator structure to enumerate the primes in the sieve. It's inspired by the golang bit packed sieve that returns a closure as an iterator. However, BCPL does not support closures, so the code uses an iterator object.

GET "libhdr"

A more efficient sieve (primes below one billion in under a minute) is provided as <code>PrimesTo</code> in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn].

𝕩≤2 ? ↕0 ; # No primes below 2

p ← 𝕊⌈√n←𝕩 # Initial primes by recursion

{{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 ⟩

≠∘Primes¨ 10⋆↕7 # Number of primes below 1e0, 1e1, ... 1e6

=={{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

=={{header|C}}==

#include <math.h>

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

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

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

using System.Collections;

using System.Collections.Generic;

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;

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;

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;

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;

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;

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;

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):

Console.WriteLine(PrimesXXX().ElementAt(1000000 - 1)); // zero based indexing...

}</syntaxhighlight>

This implementation follows the standard library pattern of [http://en.cppreference.com/w/cpp/algorithm/iota std::iota]. The start and end iterators are provided for the container. The destination container is used for marking primes and then filled with the primes which are less than the container size. This method requires no memory allocation inside the function.

#include <algorithm>

#include <vector>

=== Boost ===

template<class UnaryFunction>

void primesupto(int limit, UnaryFunction yield)

Full program:

$ g++ -I/path/to/boost sieve.cpp -o sieve && sieve 10000000

*/

{{incorrect|Chapel|Doesn't compile since at least Chapel version 1.20 to 1.24.1.}}

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

iter sieve(prime):int {

}

}</syntaxhighlight>The topmost sieve needs to be started with 2 (the smallest prime):

for p in sieve(2) {

if p > N {

compile with the `--fast` option

use BitOps;

===Alternate Odds-Only Bit-Packed Implementation===

use BitOps;

{{works with|Chapel|1.25.1}}

config const limit = 100000000;

Compile with the `--fast` compiler command line option

config const limit = 100000000;

Compile with the `--fast` compiler command line option

use Map;

{{trans|Nim}} [https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Nim_Unbounded_Versions code link]

{{works with|Chapel|1.22|- compile with the --fast compiler command line flag for full optimization}}

type Prime = uint(32);

To take advantage of the features that make Chapel shine, we need to use it to do some parallel computations, and to efficiently do that for the Sieve of Eratosthenes, we need to divide the work into page segments where we can assign each largish segment to a separate thread/task; this also improves the speed due to better cache associativity with most memory accesses to values that are already in the cache(s). Once we have divided the work, Chapel offers lots of means to implement the parallelism but to be a true Sieve of Eratosthenes, we need to have the ability to output the results in order; with many of the convenience mechanisms not doing that, the best/simplest option is likely task parallelism with the output results assigned to an rotary indexed array containing the `sync` results. It turns out that, although the Chapel compiler can sometimes optimize the code so the overhead of creating tasks is not onerous, for this case where the actual tasks are somewhat complex, the compiler can't recognize that an automatically generated thread pool(s) are required so we need to generate the thread pool(s) manually. The code that implements the multi-threading of page segments using thread pools is as follows:

{{works with|Chapel|1.24.1|- compile with the --fast compiler command line flag for full optimization}}

type Prime = uint(64);

=={{header|Clojure}}==

(remove (set (mapcat #(range (* % %) n %)

(range 2 (Math/sqrt n))))

It may be written using the ''into #{}'' function to run slightly faster due to the ''set'' function being concerned with only distinct elements whereas the ''into #{}'' only does the conjunction, and even at that doesn't do that much as it does the conjunction to an empty sequence, the code as follows:

(remove (into #{}

(mapcat #(range (* % %) n %)

The following code also uses the ''into #{}'' transducer but has been slightly wheel-factorized to sieve odds-only:

(if (< n 2) ()

(cons 2 (remove (into #{}

The following code calculates primes up to and including ''n'' using a mutable boolean array but otherwise entirely functional code; it is tens (to a hundred) times faster than the purely functional codes due to the use of mutability in the boolean array:

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

[n]

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

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

[lim]

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

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

[lim]

'''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]

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]

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

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]

'''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."

[]

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."

[]

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)

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"

[]

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 ">")))

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"

[]

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

=={{header|CLU}}==

eratosthenes = proc (n: int) returns (array[bool])

prime: array[bool] := array[bool]$fill(1, n, true)

=={{header|CMake}}==

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

# this check fails when limit > 46340.

=={{header|COBOL}}==

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

IDENTIFICATION DIVISION.

=={{header|Comal}}==

{{trans|BASIC}}

input "Limit? ": limit

dim sieve(1:limit)

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

(loop

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

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."

=={{header|Cowgol}}==

# To change the maximum prime, change the size of this array

This implementation uses a `BitArray` so it is automatically bit-packed to use just one bit per number representation:

require "bit_array"

the non-odds-only version as per the above should never be used because in not using odds-only, it uses twice the memory and over two and a half times the CPU operations as the following odds-only code, which is very little more complex:

require "bit_array"

For sieving of ranges larger than a few million efficiently, a page-segmented sieve should always be used to preserve CPU cache associativity by making the page size to be about that of the CPU L1 data cache. The following code implements a page-segmented version that is an extensible sieve (no upper limit needs be specified) using a secondary memoized feed of base prime value arrays which use a smaller page-segment size for efficiency. When the count of the number of primes is desired, the sieve is polymorphic in output and counts the unmarked composite bits by using fast `popcount` instructions taken 64-bits at a time. The code is as follows:

alias Prime = UInt64

=={{header|D}}==

===Simpler Version===

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

===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 {

===Extensible Version===

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

struct Prime {

uint[] a = [2];

=={{header|Dart}}==

String iterableToString(Iterable seq) {

String str = "[";

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

import 'dart:math';

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

{{trans|Kotlin}}

import 'dart:math';

import 'dart:collection';

=={{header|Delphi}}==

{$APPTYPE CONSOLE}

=={{header|Draco}}==

proc nonrec sieve([*] bool prime) void:

word p, c, max;

=={{header|DWScript}}==

var

n, k : Integer;

=={{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);

=={{header|EasyLang}}==

max = sqrt len prims[]

tst = 2

{{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[

===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]

===Wheel===

A 2x3 wheel gives a 50% performance gain.

(define (weratosthenes n)

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

On the EdsacPC simulator (see link above) the printout starts off very slowly, and gradually gets faster.

[Sieve of Eratosthenes]

[EDSAC program. Initial Orders 2]

=={{header|Eiffel}}==

{{works with|EiffelStudio|6.6 beta (with provisional loop syntax)}}

APPLICATION

=={{header|Elixir}}==

def eratosthenes(limit \\ 1000) do

sieve = [false, false | Enum.to_list(2..limit)] |> List.to_tuple

Shorter version (but slow):

defmodule Sieve do

def primes_to(limit), do: sieve(Enum.to_list(2..limit))

The above code has a very limited useful range due to being very slow: for example, to sieve to a million, even changing the algorithm to odds-only, requires over 800 thousand "copy-on-update" operations of the entire saved immutable tuple ("array") of 500 thousand bytes in size, making it very much a "toy" application. The following code overcomes that problem by using a (immutable/hashed) Map to store the record of the current state of the composite number chains resulting from each of the secondary streams of base primes, which are only 167 in number up to this range; it is a functional "incremental" Sieve of Eratosthenes implementation:

@typep stt :: {integer, integer, integer, Enumerable.integer, %{integer => integer}}

In order to save the computation time of computing the hashes, the following version uses a deferred execution Co-Inductive Stream type (constructed using Tuple's) in an infinite tree folding structure (by the `pairs` function):

@typep cis :: {integer, (() -> cis)}

@typep ciss :: {cis, (() -> ciss)}

The Elm language doesn't handle efficiently doing the Sieve of Eratosthenes (SoE) algorithm efficiently because it doesn't have directly accessible linear arrays and also does Copy On Write (COW) for every write to every location as well as a logarithmic process of updating as a "tree" to minimize the COW operations. Thus, there is better performance implementing the Richard Bird Tree Folding functional algorithm, as follows:

{{trans|Haskell}}

import Browser exposing (element)

Using a Binary Minimum Heap Priority Queue is a constant factor faster than the above code as the data structure is balanced rather than "heavy to the right" in the following code, which implements enough of the Priority Queue for the purpose:

import Task exposing ( Task, succeed, perform, andThen )

=={{header|Emacs Lisp}}==

{{libheader|cl-lib}}

(let ((xs (make-vector (1+ limit) 0)))

(cl-loop for i from 2 to limit

Straightforward implementation of [http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Implementation sieve of Eratosthenes], 2 times faster:

(let ((xs (vconcat [0 0] (number-sequence 2 limit))))

(cl-loop for i from 2 to (sqrt limit)

=={{header|Erlang}}==

===Erlang using Dicts===

-module( sieve_of_eratosthenes ).

Has the virtue of working for any -> N :)

-module( sieve ).

-export( [main/1,primes/2] ).

Since I had written a really odd and slow one, I thought I'd best do a better performer. Inspired by an example from https://github.com/jupp0r

-module(ossieve).

A pure list comprehension approach.

-module(sieveof).

-export([main/1,primes/1, primes/2]).

===Erlang ets + cpu distributed implementation ===

much faster previous erlang examples

#!/usr/bin/env escript

%% -*- erlang -*-

=={{header|ERRE}}==

PROGRAM SIEVE_ORG

! --------------------------------------------------

=={{header|Euphoria}}==

sequence flags,primes

flags = repeat(1, limit)

=={{header|F Sharp}}==

===Short with mutable state===

let primes max =

let mutable xs = [|2..max|]

===Short Sweet Functional and Idiotmatic===

Well lists may not be lazy, but if you call it a sequence then it's a lazy list!

(*

An interesting implementation of The Sieve of Eratosthenes.

This is the idea behind Richard Bird's unbounded code presented in the Epilogue of [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf M. O'Neill's article] in Haskell. It is about twice as much code as the Haskell code because F# does not have a built-in lazy list so that the effect must be constructed using a Co-Inductive Stream (CIS) type since no memoization is required, along with the use of recursive functions in combination with sequences. The type inference needs some help with the new CIS type (including selecting the generic type for speed). Note the use of recursive functions to implement multiple non-sharing delayed generating base primes streams, which along with these being non-memoizing means that the entire primes stream is not held in memory as for the original Bird code:

let primesBird() =

The above code sieves all numbers of two and up including all even numbers as per the page specification; the following code makes the very minor changes for an odds-only sieve, with a speedup of over a factor of two:

let primesBirdOdds() =

The above code is still somewhat inefficient as it operates on a linear right extending structure that deepens linearly with increasing base primes (those up to the square root of the currently sieved number); the following code changes the structure into an infinite binary tree-like folding by combining each pair of prime composite streams before further processing as usual - this decreases the processing by approximately a factor of log n:

let primesTreeFold() =

In order to investigate Priority Queue Sieves as espoused by O'Neill in the referenced article, one must find an equivalent implementation of a Min Heap Priority Queue as used by her. There is such an purely functional implementation [http://rosettacode.org/wiki/Priority_queue#Functional in RosettaCode translated from the Haskell code she used], from which the essential parts are duplicated here (Note that the key value is given an integer type in order to avoid the inefficiency of F# in generic comparison):

module MinHeap =

Except as noted for any individual code, all of the following codes need the following prefix code in order to implement the non-memoizing Co-Inductive Streams (CIS's) and to set the type of particular constants used in the codes to the same time as the "Prime" type:

type Prime = uint32

let frstprm = 2u

The F# equivalent to O'Neill's "odds-only" code is then implemented as follows, which needs the included changed prefix in order to change the primes type to a larger one to prevent overflow (as well the key type for the MinHeap needs to be changed from uint32 to uint64); it is functionally the same as the O'Neill code other than for minor changes to suit the use of CIS streams and the option output of the "peekMin" function:

type Prime = uint64

let frstprm = 2UL

However, that algorithm suffers in speed and memory use due to over-eager adding of prime composite streams to the queue such that the queue used is much larger than it needs to be and a much larger range of primes number must be used in order to avoid numeric overflow on the square of the prime added to the queue. The following code corrects that by using a secondary (actually a multiple of) base primes streams which are constrained to be based on a prime that is no larger than the square root of the currently sieved number - this permits the use of much smaller Prime types as per the default prefix:

let rec nxtprm n pq q (bps: CIS<Prime>) =

if n >= q then let bp = bps.v in let adv = bp + bp

The following code is written in functional style other than it uses a mutable bit array to sieve the composites:

let buf = System.Collections.BitArray(int limit + 1, true)

let cull p = { p * p .. p .. limit } |> Seq.iter (fun c -> buf.[int c] <- false)

Substituting the following minor changes to the code for the "primes" function will only deal with the odd prime candidates for a speed up of over a factor of two as well as a reduction of the buffer size by a factor of two:

let lmtb,lmtbsqrt = (limit - 3u) / 2u, (uint32 (sqrt (double limit)) - 3u) / 2u

let buf = System.Collections.BitArray(int lmtb + 1, true)

The following code uses other functional forms for the inner culling loops of the "primes function" to reduce the use of inefficient sequences so as to reduce the execution time by another factor of almost three:

let lmtb,lmtbsqrt = (limit - 3u) / 2u, (uint32 (sqrt (double limit)) - 3u) / 2u

let buf = System.Collections.BitArray(int lmtb + 1, true)

Now much of the remaining execution time is just the time to enumerate the primes as can be seen by turning "primes" into a primes counting function by substituting the following for the last line in the above code doing the enumeration; this makes the code run about a further five times faster:

if i > int lmtb then acc else if buf.[i] then count (i + 1) (acc + 1) else count (i + 1) acc

count 0 1</syntaxhighlight>

Since the final enumeration of primes is the main remaining bottleneck, it is worth using a "roll-your-own" enumeration implemented as an object expression so as to save many inefficiencies in the use of the built-in seq computational expression by substituting the following code for the last line of the previous codes, which will decrease the execution time by a factor of over three (instead of almost five for the counting-only version, making it almost as fast):

let i = ref -2

let rec nxti() = i:=!i + 1;if !i <= int lmtb && not buf.[!i] then nxti() else !i <= int lmtb

The following code uses the DotNet Dictionary class instead of the above functional Priority Queue to implement the sieve; as average (amortized) hash table access is O(1) rather than O(log n) as for the priority queue, this implementation is slightly faster than the priority queue version for the first million primes and will always be faster for any range above some low range value:

let frstprm = 2u

let frstoddprm = 3u

All of the above unbounded implementations including the above Dictionary based version are quite slow due to their large constant factor computational overheads, making them more of an intellectual exercise than something practical, especially when larger sieving ranges are required. The following code implements an unbounded page segmented version of the sieve in not that many more lines of code, yet runs about 25 times faster than the Dictionary version for larger ranges of sieving such as to one billion; it uses functional forms without mutability other than for the contents of the arrays and the `primes` enumeration generator function that must use mutability for speed:

type private PrimeNdx = float // they are slow in JavaScript polyfills

Factor is pleasantly multiparadigm. Usually, it's natural to write more functional or declarative code in Factor, but this is an instance where it is more natural to write imperative code. Lexical variables are useful here for expressing the necessary mutations in a clean way.

math.ranges prettyprint sequences ;

IN: rosetta-code.sieve-of-erato

=={{header|FOCAL}}==

1.2 A N

1.3 I (2047-N)5.1

The above code is not really very good Forth style as the main initialization, sieving, and output, are all in one `sieve` routine which makes it difficult to understand and refactor; Forth code is normally written in a series of very small routines which makes it easier to understand what is happening on the data stack, since Forth does not have named local re-entrant variable names as most other languages do for local variables (which other languages also normally store local variables on the stack). Also, it uses the `HERE` pointer to user space which points to the next available memory after all compilation is done as a unsized buffer pointer, but as it does not reserve that space for the sieving buffer, it can be changed by other concatenated routines in unexpected ways; better is to allocate the sieving buffer as required from the available space at the time the routines are run and pass that address between concatenated functions until a finalization function frees the memory and clears the stack; this is equivalent to allocating from the "heap" in other languages. The below code demonstrates these ideas:

\ given square index and prime index, u0, sieve the multiples of said prime...

Although the above version resolves many problems of the first version, it is wasteful of memory as each composite number in the sieve buffer is a byte of eight bits representing a boolean value. The memory required can be reduced eight-fold by bit packing the sieve buffer; this will take more "bit-twiddling" to read and write the bits, but reducing the memory used will give better cache assiciativity to larger ranges such that there will be a net gain in performance. This will make the code more complex and the stack manipulations will be harder to write, debug, and maintain, so ANS Forth 1994 provides a local variable naming facility to make this much easier. The following code implements bit-packing of the sieve buffer using local named variables when required:

: numbts ( u -- u ) \ pop count number of bits...

0 SWAP BEGIN DUP 0<> WHILE SWAP 1+ SWAP DUP 1- AND REPEAT DROP ;

While the above version does greatly reduce the amount of memory used for a given sieving range and thereby also somewhat reduces execution time; any sieve intended for sieving to limits of a hundred million or more should use a page-segmented implementation; page-segmentation means that only storage for a representation of the base primes up to the square root of the limit plus a sieve buffer that should also be at least proportional to the same square root is required; this will again make the execution faster as ranges go up due to better cache associativity with most memory accesses being within the CPU cache sizes. The following Forth code implements a basic version that does this:

1 17 LSHIFT CONSTANT L1CacheBits

L1CacheBits 8 * CONSTANT L2CacheBits

=={{header|Fortran}}==

{{works with|Fortran|77}}

PROGRAM MAIN

INTEGER LI

{{works with|Fortran|90 and later}}

implicit none

end program sieve</syntaxhighlight>

Output:

Because it uses four byte logical's (default size) as elements of the sieve buffer, the above code uses 400 bytes of memory for this trivial task of sieving to 100; it also has 49 + 31 + 16 + 8 = 104 (for the culling by the primes of two, three, five, and seven) culling operations.

'''Optimised using a pre-computed wheel based on 2:'''

implicit none

end program sieve_wheel_2</syntaxhighlight>

Output:

This so-called "optimized" version still uses 400 bytes of memory but slightly reduces to 74 operations from 104 operations including the initialization of marking all of the even representations as composite due to skipping the re-culling of the even representation, so isn't really much of an optimization at all!

The above implementations, especially the second odds-only code, are some of the most inefficient versions of the Sieve of Eratosthenes in any language here as to time and space efficiency, only worse by some naive JavaScript implementations that use eight-byte Number's as logical values; the second claims to be wheel factorized but still uses all the same memory as the first and still culls by the even numbers in the initialization of the sieve buffer. As well, using four bytes (default logical size) to store a boolean value is terribly wasteful if these implementations were to be extended to non-toy ranges. The following code implements proper wheel factorization by two, reducing the space used by a factor of about eight to 49 bytes by using `byte` as the sieve buffer array elements and not requiring the evens initialization, thus reducing the number of operations to 16 + 8 + 4 = 28 (for the culling primes of three, five, and seven) culling operations:

implicit none

The above implementation is still space inefficient in effectively only using one bit out of eight; the following version implements bit packing to reduce memory use by a factor of eight by using bits to represent composite numbers rather than bytes:

implicit none

As well as adding page-segmentation, the following code adds multi-processing which is onc of the capabilities for which modern Fortran is known:

implicit none

===Basic version===

function Sieve returns a list of primes less than or equal to the given aLimit

program prime_sieve;

{$mode objfpc}{$coperators on}

===Alternative segmented(odds only) version===

function OddSegmentSieve returns a list of primes less than or equal to the given aLimit

program prime_sieve;

{$mode objfpc}{$coperators on}

=={{header|FreeBASIC}}==

Sub sieve(n As Integer)

=={{header|Frink}}==

n = eval[input["Enter highest number: "]]

results = array[sieve[n]]

''Note: With benchmark function''

tick sto startingtick

#g 100000 sto MAX

=={{header|FutureBasic}}==

===Basic sieve of array of booleans===

begin globals

=={{header|GAP}}==

local a, i, j;

a := ListWithIdenticalEntries(n, true);

=={{header|GLBasic}}==

// GLBasic implementation

=={{header|Go}}==

===Basic sieve of array of booleans===

import "fmt"

The above version's output is rather specialized; the following version uses a closure function to enumerate over the culled composite number array, which is bit packed. By using this scheme for output, no extra memory is required above that required for the culling array:

import (

===Sieve Tree===

A fairly odd sieve tree method:

import "fmt"

===Concurrent Daisy-chain sieve===

A concurrent prime sieve adopted from the example in the "Go Playground" window at http://golang.org/

import "fmt"

===Postponed Concurrent Daisy-chain sieve===

Here we postpone the ''creation'' of filters until the prime's square is seen in the input, to radically reduce the amount of filter channels in the sieve chain.

import "fmt"

===Incremental Odds-only Sieve===

Uses Go's built-in hash tables to store odd composites, and defers adding new known composites until the square is seen.

package main

=={{header|Groovy}}==

This solution uses a BitSet for compactness and speed, but in [[Groovy]], BitSet has full List semantics. It also uses both the "square root of the boundary" shortcut and the "square of the prime" shortcut.

def isPrime = new BitSet(bound)

isPrime[0..1] = false

Test:

Output:

=={{header|GW-BASIC}}==

20 DIM FLAGS(LIMIT)

30 FOR N = 2 TO SQR (LIMIT)

Mutable array of unboxed <code>Bool</code>s indexed by <code>Int</code>s:

{-# OPTIONS_GHC -O2 #-}

Mutable array of unboxed <code>Bool</code>s indexed by <code>Int</code>s, representing odds only:

import Control.Monad.ST

import Data.Array.ST

The reason for this alternate version is to have an accessible version of "odds only" that uses the same optimizations and is written in the same coding style as the basic version. This can be used by just substituting the following code for the function of the same name in the first base example above. Mutable array of unboxed <code>Bool</code>s indexed by <code>Int</code>s, representing odds only:

primesTo limit

| limit < 2 = []

===Immutable arrays===

Monolithic sieving array. ''Even'' numbers above 2 are pre-marked as composite, and sieving is done only by ''odd'' multiples of ''odd'' primes:

primesToA m = sieve 3 (array (3,m) [(i,odd i) | i<-[3..m]] :: UArray Int Bool)

Works by segments between consecutive primes' squares. Should be the fastest of non-monadic code. ''Evens'' are entirely ignored:

primesSA = 2 : prs ()

===Basic list-based sieve===

Straightforward implementation of the sieve of Eratosthenes in its original bounded form. This finds primes in gaps between the composites, and composites as an enumeration of each prime's multiples.

eratos (p : xs)

| p*p > m = p : xs

===Unbounded list based sieve===

Unbounded, "naive", too eager to subtract (see above for the definition of <code>minus</code>):

where

sieve (p:xs) = p : sieve (minus xs [p, p+p..])

The number of active streams can be limited to what's strictly necessary by postponement until the square of a prime is seen, getting a massive complexity improvement to better than <i>~ n^1.5</i> so it can get first million primes or so in a tolerable time:

where

sieve (x:xs) q (p:t)

Transposing the workflow, going by segments between the consecutive squares of primes:

primesSE = 2 : sieve 3 4 (tail primesSE) (inits primesSE)

The basic gradually-deepening left-leaning <code>(((a-b)-c)- ... )</code> workflow of <code>foldl minus a bs</code> above can be rearranged into the right-leaning <code>(a-(b+(c+ ... )))</code> workflow of <code>minus a (foldr union [] bs)</code>. This is the idea behind Richard Bird's unbounded code presented in [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf M. O'Neill's article], equivalent to:

-- = _Y ( (2:) . minus [3..] . _LU . map(\p-> [p*p, p*p+p..]) )

This merges primes' multiples streams in a ''tree''-like fashion, as a sequence of balanced trees of <code>union</code> nodes, likely achieving theoretical time complexity only a ''log n'' factor above the optimal ''n log n log (log n)'', for ''n'' primes produced. Indeed, empirically it runs at about ''~ n^1.2'' (for producing first few million primes), similarly to priority-queue&ndash;based version of M. O'Neill's, and with very low space complexity too (not counting the produced sequence of course):

primes() = 2 : _Y ((3:) . gaps 5 . _U . map(\p-> [p*p, p*p+2*p..])) where

_Y g = g (_Y g) -- = g (g (g ( ... ))) non-sharing multistage fixpoint combinator

====With Wheel====

Using <code>_U</code> defined above,

primesW = [2,3,5,7] ++ _Y ( (11:) . gapsW 13 (tail wheel) . _U .

map (\p->

2. Improving the means to re-generate the position on the wheel for the recursive base primes without the use of `dropWhile`, etc. The below improved code uses a copy of the place in the wheel for each found base prime for ease of use in generating the composite number to-be-culled chains.

wheelGen :: Int -> ([Int],Int,[Int])

wheelGen n = loop 1 3 [2] [2] where