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

 

In order to implement a Priority Queue version with Haskell, an efficient Priority Queue, which is not part of the standard Haskell libraries, is required. A Min Heap implementation is likely best suited for this task in providing the most efficient frequently used peeks of the next item in the queue and replacement of the first item in the queue (not using a "pop" followed by a "push) with "pop" operations then not used at all, and "push" operations used relatively infrequently. Judging by O'Neill's use of an efficient "deleteMinAndInsert" operation which she states "(We provide deleteMinAndInsert becausea heap-based implementation can support this operation with considerably less rearrangement than a deleteMin followed by an insert.)", which statement is true for a Min Heap Priority Queue and not others, and her reference to a priority queue by (Paulson, 1996), the queue she used is likely the one as provided as a simple true functional [http://rosettacode.org/wiki/Priority_queue#Haskell Min Heap implementation on RosettaCode], from which the essential functions are reproduced here:

| Br !k v !(PriorityQ k v) !(PriorityQ k v)

deriving (Eq, Ord, Read, Show)

 

The following code is O'Neill's original odds-only code (without wheel factorization) from her paper slightly adjusted as per the requirements of this Min Heap implementation as laid out above; note the `seq` adjustments to the "adjust" function to make the evaluation of the entry tuple more strict for better efficiency:

-- this copyright message is retained and changed versions of the file

-- are clearly marked.

 

The following code is adjusted to reduce the amount of lazy list processing and to add a secondary base primes stream (or a succession of streams when the combinator is used) so as to overcome the above problems and reduce memory consumption to only that required for the primes below the square root of the currently sieved number; using this means that 32-bit Int's are sufficient for a reasonable range and memory requirements become relatively negligible:

primesPQx() = 2 : _Y ((3 :) . sieve 5 emptyPQ 9) -- initBasePrms

where

Since the Tree-Folding version above includes the minor changes to work with a factorization wheel, this should have the same minor modifications for comparison purposes, with the code as follows:

 

 

primesPQWheeled :: () -> [Int]

 

All of the above unbounded sieves are quite limited in practical sieving range due to the large constant factor overheads in computation, making them mostly just interesting intellectual exercises other than for small ranges of up to about the first million to ten million primes; the following '''"odds-only"''' page-segmented version using (bit-packed internally) mutable unboxed arrays is about 50 times faster than the fastest of the above algorithms for ranges of about that and higher, making it practical for the first several hundred million primes:

 

import Data.Int ( Int64 )

To show the limitations of the individual prime enumeration, the following code has been refactored from the above to provide an alternate very fast method of counting the unset bits in the culled array (the primes = none composite) using a CPU native pop count instruction:

 

{-# OPTIONS_GHC -O2 -fllvm #-} -- use LLVM for about double speed!

 

===APL-style===

Rolling set subtraction over the rolling element-wise addition on integers. Basic, slow, worse than quadratic in the number of primes produced, empirically:

. scanl1 minus

. scanl1 (zipWith (+)) $ repeat [2..]</syntaxhighlight>

Or, a wee bit faster:

. tail) $ a)

. scanl1 (zipWith (+)) $ repeat [2..]</syntaxhighlight>

A bit optimized, much faster, with better complexity,

. unfoldr (\(a:b:t) -> Just . second ((:t) . (`minus` b))

. span (< head b) $ a)

 

getting nearer to the functional equivalent of the <code>primesPE</code> above, i.e.

. unfoldr (\(a:b:t) -> Just . second ((:t) . (`minus` b))

. span (< head b) $ a)

 

An illustration:

[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

[ 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32]

 

=={{header|HicEst}}==

 

sieve = $ > 1 ! = 0 1 1 1 1 ...

 

=={{header|Hoon}}==

!:

|= end=@ud

 

=={{header|Icon}} and {{header|Unicon}}==

sieve(100)

end

 

Alternatively using sets

sieve(100)

end

{{eff note|J|i.&.(p:inv) }}

 

r=. 0#t=. y# j=.1

while. y>j=.j+1 do.

Example:

 

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</syntaxhighlight>

 

To see into how this works, we can change the definition:

 

r=. 0#t=. y# j=.1

while. y>j=.j+1 do.

}}</syntaxhighlight>

 

┌─┬───────────────────┬───────────────────┐

│2│1 0 1 0 1 0 1 0 1 0│0 1 0 1 0 1 0 1 0 1│

This is based off the Python version.

 

"Gives all the primes < limit"

[limit]

=={{header|Java}}==

{{works with|Java|1.5+}}

 

public class Sieve{

 

To optimize by testing only odd numbers, replace the loop marked "unoptimized" with these lines:

for(int i = 3;i <= n;i += 2){

nums.add(i);

 

Version using List:

import java.util.ArrayList;

import java.util.List;

</syntaxhighlight>

Version using a BitSet:

import java.util.BitSet;

 

 

Version using a TreeSet:

import java.util.TreeSet;

 

{{trans|Python}}

{{works with|Java|1.5+}}

import java.util.PriorityQueue;

import java.math.BigInteger;

{{trans|Python}}

{{works with|Java|1.5+}}

import java.util.HashMap;

{{trans|JavaScript}}

{{works with|Java|1.5+}}

import java.util.ArrayList;

 

 

=={{header|JavaScript}}==

var primes = [];

if (limit >= 2) {

Substituting the following code for the function for '''an odds-only algorithm using bit packing''' for the array produces code that is many times faster than the above:

 

var prms = [];

if (limit >= 2) prms = [2];

While the above code is quite fast especially using an efficient JavaScript engine such as Google Chrome's V8, it isn't as elegant as it could be using the features of the new EcmaScript6 specification when it comes out about the end of 2014 and when JavaScript engines including those of browsers implement that standard in that we might choose to implement an incremental algorithm iterators or generators similar to as implemented in Python or F# (yield). Meanwhile, we can emulate some of those features by using a simulation of an iterator class (which is easier than using a call-back function) for an '''"infinite" generator based on an Object dictionary''' as in the following odds-only code written as a JavaScript class:

 

function SoEIncClass() {

this.n = 0;

The above code can be used to find the nth prime (which would require estimating the required range limit using the previous fixed range code) by using the following code:

 

for (var i = 1; i < 1000000; i++, gen.next());

var prime = gen.next();

This can be implemented as '''an "infinite" odds-only generator using page segmentation''' for a considerable speed-up with the alternate JavaScript class code as follows:

 

function SoEPgClass() {

this.bi = -1; // constructor resets the enumeration to start...

 

function is copy-pasted from above to produce a webpage version for beginners:

<script>

function eratosthenes(limit) {

 

=={{header|JOVIAL}}==

START

FILE MYOUTPUT ... $ ''Insufficient information to complete this declaration''

Short and sweet ...

 

# eratosthenes/0 produces an array of primes less than or equal to $n:

def eratosthenes:

| map(select(.));</syntaxhighlight>

'''Examples''':

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

{{out}}

664579

 

Started with 2 already in the array, and then test only for odd numbers and push the prime ones onto the array.

function sieve(lim :: Int)

if lim < 2 return [] end

Alternate version using <code>findall</code> to get all primes at once in the end

 

isprime = trues(n)

isprime[1] = false

If one is going to "crib" the MatLab algorithm as above, one may as well do it using odds-only as per the MatLab built-in. The following alternate code improves on the "Alternate" example above by making it sieve odds-only and adjusting the result array contents after to suit:

 

ni = (n - 1) ÷ 2

isprime = trues(ni)

The creation of an output results array is not necessary if the purpose is just to scan across the resulting primes once, they can be output using an iterator (from a `BitArray`) as in the following odds-only code:

 

 

struct Primes

for which using the following code:

 

@time length(Primes(100)) # warm up JIT

# println(@time count(x->true, Primes(1000000000))) # about 1.5 seconds slower counting over iteration

For any kind of reasonably large range such as a billion, a page segmented version should be used with the pages sized to the CPU caches for much better memory access times. As well, the following odds-only example uses a custom bit packing algorithm for a further two times speed-up, also reducing the memory allocation delays by reusing the sieve buffers when possible (usually possible):

 

const BasePrime = UInt32

const BasePrimesArray = Array{BasePrime,1}

When tested with the following code:

 

print("( ")

for p in PrimesPaged() p > 100 && break; print(p, " ") end

One of the best simple purely functional Sieve of Eratosthenes algorithms is the infinite tree folding sequence algorithm as implemented in Haskell. As Julia does not have a standard LazyList implementation or library and as a full memoizing lazy list is not required for this algorithm, the following odds-only code implements the rudiments of a Co-Inductive Stream (CIS) in its implementation:

 

 

struct CIS{T}

when tested with the following:

 

 

it outputs the following:

To gain some extra speed above the purely functional algorithm above, the Python'ish version as a mutable iterator embedding a mutable standard base Dictionary can be used. The following version uses a secondary delayed injection stream of "base" primes defined recursively to provide the successions of composite values in the Dictionary to be used for sieving:

 

abstract type PrimesDictAbstract end # used for forward reference

mutable struct PrimesDict <: PrimesDictAbstract

 

=={{header|Klingphix}}==

 

%limit %i

 

=={{header|Kotlin}}==

 

fun sieve(max: Int): List<Int> {

The following code overcomes most of those problems: It only culls odd composites; it culls a bit-packed primitive array (also saving memory); It uses tailcall recursive functions for the loops, which are compiled into simple loops. It also outputs the results as an enumeration, which isn't fast but does not consume any more memory than the culling array. In this way, the program is only limited in sieving range by the maximum size limit of the culling array, although as it grows larger than the CPU cache sizes, it loses greatly in speed; however, that doesn't matter so much if just enumerating the results.

 

val topi = (rng - 3) shr 1

val lstw = topi shr 5

Ah, one might say, for such a trivial range one writes for conciseness and not for speed. Well, I say, one can still save memory and some time using odds-only and a bit-packed array, but write very clear and concise (but slower) code using nothing but higher order functions and function calling. The following code using such techniques can use the same "main" function for the same output but is about two times slower, mostly due to the extra time spent making (nested) function calls, including the function calls necessary for enumeration. Note that the effect of using the "(l .. h).forEach { .. }" is the same as the "for i in l .. h { .. }" as both use an iteration across the range but the second is just syntax sugar to make it look more imperative:

 

val topi = (rng - 3) / 2 //convert to nearest index

val size = topi / 32 + 1 //word size to include index

The trouble with the above version is that, at least for Kotlin version 1.0, the ".filter" and ".map" extension functions for Iterable<Int> create Java "ArrayList"'s as their output (which are wrapped to return the Kotlin "List<Int>" interface), thus take a considerable amount of memory worse than the first version (using an ArrayList to store the resulting primes), since as the calculations are chained to ".map", require a second ArrayList of up to the same size while the mapping is being done. The following version uses Sequences , which aren't backed by any permanent structure, but it is another small factor slower due to the nested function calls:

 

val topi = (rng - 3) / 2 //convert to nearest index

val size = topi / 32 + 1 //word size to include index

 

The following Sieve of Eratosthenes is not purely functional in that it uses a Mutable HashMap to store the state of succeeding composite numbers to be skipped over, but embodies the principles of an incremental implementation of the Sieve of Eratosthenes sieving odds-only and is faster than most incremental sieves due to using mutability. As with the fastest of this kind of sieve, it uses a delayed secondary primes feed as a source of base primes to generate the composite number progressions. The code as follows:

yield(2)

fun oddprms(): Sequence<Int> = sequence {

 

At about 370 clock cycles per culling operation (about 3,800 cycles per prime) on my tablet class Intel CPU, this is not blazing fast but adequate for ranges of a few millions to a hundred million and thus fine for doing things like solving Euler problems. For instance, Euler Problem 10 of summing the primes to two million can be done with the following "one-liner":

 

to output the correct answer of the following in about 270 milliseconds for my Intel x5-Z8350 at 1.92 Gigahertz:

{{trans|Haskell}}

 

fun toSequence() = generateSequence(this) { it.tailf() } .map { it.head }

}

 

The very fastest implementations of a primes sieve are all based on bit-packed mutable arrays which can be made unbounded by setting them up so that they are a succession of sieved bit-packed arrays that have been culled of composites. The following code is an odds=only implementation that, again, uses a secondary feed of base primes that is only expanded as necessary (in this case memoized by a rudimentary lazy list structure to avoid recalculation for every base primes sweep per page segment):

internal typealias BasePrime = Int

internal typealias BasePrimeArray = IntArray

 

=={{header|Lambdatalk}}==

{def sieve

 

=={{header|langur}}==

{{trans|D}}

if .limit < 2 {

return []

 

=={{header|Liberty BASIC}}==

'The sieve() function uses the flags() array.

'This is a Sieve benchmark adapted from BYTE 1985

 

=={{header|Limbo}}==

 

include "sys.m";

 

=={{header|Lingo}}==

property _sieve

 

end</syntaxhighlight>

 

put sieve.getPrimes(100)</syntaxhighlight>

 

 

=={{header|LiveCode}}==

set itemdel to comma

local sieve

return sieve

end sieveE</syntaxhighlight>

-- 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,101,103,107,109,113</syntaxhighlight>

 

 

 

# calculates prime numbers up to a given number

due to the use of mod (modulo = division) in the filter function.

A coinduction based solution just for fun:

:- object(sieve).

 

</syntaxhighlight>

Example query:

?- sieve::primes(20, P).

P = [2, 3|_S1], % where

 

=={{header|LOLCODE}}==

CAN HAS STDIO?

 

 

=={{header|Lua}}==

if n < 2 then return {} end

local t = {0} -- clears '1'

 

The following changes the code to '''odds-only''' using the same large array-based algorithm:

if n < 2 then return {} end

if n < 3 then return {2} end

The following code implements '''an odds-only "infinite" generator style using a table as a hash table''', including postponing adding base primes to the table:

 

local _cand = 0; local _lstbp = 3; local _lstsqr = 9

local _composites = {}; local _bps = nil

 

=={{header|M2000 Interpreter}}==

Module EratosthenesSieve (x) {

\\ Κόσκινο του Ερατοσθένη

 

=={{header|M4}}==

define(`for',

`ifelse($#,0,

=={{header|MAD}}==

 

R TO GENERATE MORE PRIMES, CHANGE BOTH THESE NUMBERS

 

=={{header|Maple}}==

local numbers_to_check, i, k;

numbers_to_check := [seq(2 .. n)];

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Do[If[numbers[[i]] != 0, Do[numbers[[i j]] = 0, {j, 2, n/i}]], {i,

2, Sqrt[n]}];

===Slightly Optimized Version===

The below has been improved to not require so many operations per composite number cull for about two thirds the execution time:

Do[If[numbers[[i]] != 0, Do[numbers[[j]] = 0, {j,i i,n,i}]],{i,2,Sqrt[n]}];

Select[numbers, # > 1 &]]

===Sieving Odds-Only Version===

The below has been further improved to only sieve odd numbers for a further reduction in execution time by a factor of over two:

Do[c = numbers[[i]]; If[c != 0,

Do[numbers[[j]] = 0, {j,(c c - 1)/2,limit,c}]], {i,1,(Sqrt[n] - 1)/2}];

=={{header|MATLAB}} / {{header|Octave}}==

===Somewhat optimized true Sieve of Eratosthenes===

P = [0 2:x]; % Create vector with all ints between 2 and x where

A more efficient Sieve avoids creating a large double precision vector P, instead using a logical array (which consumes 1/8 the memory of a double array of the same size) and only converting to double those values corresponding to primes.

 

ISP = [false true(1, x-1)]; % 1 is not prime, but we start off assuming all numbers between 2 and x are

for n = 2:sqrt(x)

 

=={{header|Maxima}}==

[a:makelist(true,n),i:1,j],

a[1]:false,

 

=={{header|Mercury}}==

:- interface.

:- import_module io.

=={{header|Microsoft Small Basic}}==

{{trans|GW-BASIC}}

TextWindow.Write("Enter number to search to: ")

limit = TextWindow.ReadNumber()

 

=={{header|Modula-2}}==

FROM InOut IMPORT WriteCard, WriteLn;

FROM MathLib IMPORT sqrt;

===Regular version===

This version runs slow because of the way I/O is implemented in the CM3 compiler. Setting <code>ListPrimes = FALSE</code> achieves speed comparable to C on sufficiently high values of <code>LastNum</code> (e.g., 10^6).

 

IMPORT IO;

===Advanced version===

This version uses more "advanced" types.

 

MODULE Sieve EXPORTS Main;

 

=={{header|MUMPS}}==

;performs the Sieve of Erotosethenes up to the number passed in.

;This version sets an array containing the primes

 

=={{header|Neko}}==

http://shootout.alioth.debian.org/

 

=={{header|NetRexx}}==

===Version 1 (slow)===

 

options replace format comments java crossref savelog symbols binary

</pre>

===Version 2 (significantly, i.e. 10 times faster)===

* Essential improvements:Use boolean instead of Rexx for sv

* and remove methods isTrue and isFalse

Note that the lambda expression in the following script does not involve a closure; newLISP has dynamic scope, so it matters that the same variable names will not be reused for some other purpose (at runtime) before the anonymous function is called.

 

 

; The initial sieve is a list of all the numbers starting at 2.

 

=={{header|Nim}}==

iterator primesUpto(limit: int): int =

The above version wastes quite a lot of memory by using a sequence of boolean values to sieve the composite numbers and sieving all numbers when two is the only even prime. The below code uses a bit-packed sequence to save a factor of eight in memory and also sieves only odd primes for another memory saving by a factor of two; it is also over two and a half times faster due to reduced number of culling operations and better use of the CPU cache as a little cache goes a lot further - this better use of cache is more than enough to make up for the extra bit-packing shifting operations:

 

let topndx = int((top - 3) div 2)

let sqrtndx = (int(sqrt float64(top)) - 3) div 2

 

For many purposes, one doesn't know the exact upper limit desired to easily use the above versions; in addition, those versions use an amount of memory proportional to the range sieved. In contrast, unbounded versions continuously update their range as they progress and only use memory proportional to the secondary base primes stream, which is only proportional to the square root of the range. One of the most basic functional versions is the TreeFolding sieve which is based on merging lazy streams as per Richard Bird's contribution to incremental sieves in Haskell, but which has a much better asymptotic execution complexity due to the added tree folding. The following code is a version of that in Nim (odds-only):

from times import epochTime

 

 

To show the cost of functional forms of code, the following code is written embracing mutability, both by using a mutable hash table to store the state of incremental culling by the secondary stream of base primes and by using mutable values to store the state wherever possible, as per the following code:

 

type PrimeType = int

 

For the highest speeds, one needs to use page segmented mutable arrays as in the bit-packed version here:

 

from times import epochTime # for testing

=={{header|Niue}}==

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

[ 1 + 'count ; [ <2 [ , ] when ] count times ] 'fill-stack ;

 

 

=={{header|Oberon-2}}==

 

IMPORT Out, Math;

=={{header|OCaml}}==

===Imperative===

let is_prime = Array.create n true in

let limit = truncate(sqrt (float (n - 1))) in

is_prime</syntaxhighlight>

 

let primes, _ =

let sieve = sieve n in

 

===Functional===

let fold_iter f init a b =

let rec aux acc i =

</syntaxhighlight>

in the top-level:

- : int list =

[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;

This uses zero to denote struck-out numbers. It is slightly inefficient as it strikes-out multiples above p rather than p²

 

| [] -> []

| h :: t ->

</syntaxhighlight>

in the top-level:

- : int list =

[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;

=={{header|Oforth}}==

 

| i j |

ListBuffer newSize(n) dup add(null) seqFrom(2, n) over addAll

 

=={{header|Ol}}==

(define all (iota 999 2))

 

=={{header|Oz}}==

{{trans|Haskell}}

fun {Sieve N}

S = {Array.new 2 N true}

 

=={{header|PARI/GP}}==

my(v=Vecsmall(lim\1,unused,1));

forprime(p=2,sqrt(lim),

An alternate version:

 

{

v=vector(n,unused,1);

=={{header|Pascal}}==

Note: Some Pascal implementations put quite low limits on the size of a set (e.g. Turbo Pascal doesn't allow more than 256 members). To compile on such an implementation, reduce the constant PrimeLimit accordingly.

program primes(output)

 

Using growing wheel to fill array for sieving for minimal unmark operations.

Sieving only with possible-prime factors.

program prim(output);

//Sieve of Erathosthenes with fast elimination of multiples of small primes

 

===Classic Sieve===

my $n = shift;

my @composite;

 

===Odds only (faster)===

my($n) = @_;

return @{([],[],[2],[2,3],[2,3])[$n]} if $n <= 4;

 

===Odds only, using vectors for lower memory use===

my($end) = @_;

return @{([],[],[2],[2,3],[2,3])[$end]} if $end <= 4;

===Odds only, using strings for best performance===

Compared to array versions, about 2x faster (with 5.16.0 or later) and lower memory. Much faster than the experimental versions below. It's possible a mod-6 or mod-30 wheel could give more improvement, though possibly with obfuscation. The best next step for performance and functionality would be segmenting.

my ($n, $i, $s, $d, @primes) = (shift, 7);

 

 

This older version uses half the memory, but at the expense of a bit of speed and code complexity:

my($end) = @_;

return @{([],[],[2],[2,3],[2,3])[$end]} if $end <= 4;

 

Golfing a bit, at the expense of speed:

grep { not $s[ $i = $_ ] and do

{ $s[ $i += $_ ]++ while $i <= $_[0]; 1 }

 

Or with bit strings (much slower than the vector version above):

grep { not vec $s, $i = $_, 1 and do

{ (vec $s, $i += $_, 1) = 1 while $i <= $_[0]; 1 }

 

A short recursive version:

my $p = shift;

return $p, $p**2 > $_[$#_] ? @_ : erat(grep $_%$p, @_)

print join ', ' => erat 2..100000;</syntaxhighlight>

 

my ($s, $p) = "." . ("x" x shift);

 

 

Here are two incremental versions, which allows one to create a tied array of primes:

use warnings;

package Tie::SieveOfEratosthenes;

1;</syntaxhighlight>

This one is based on the vector sieve shown earlier, but adds to a list as needed, just sieving in the segment. Slightly faster and half the memory vs. the previous incremental sieve. It uses the same API -- arguably we should be offset by one so $primes[$n] returns the $n'th prime.

use warnings;

package Tie::SieveOfEratosthenes;

=={{header|Phix}}==

{{Trans|Euphoria}}

<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>

 

=={{header|Phixmonti}}==

 

def sequence /# ( ini end [step] ) #/

 

Another solution

1000

 

=={{header|PHP}}==

function iprimes_upto($limit)

{

=={{header|Picat}}==

The SoE is provided in the standard library, defined as follows:

primes(N) = L =>

A = new_array(N),

</pre>

=={{header|PicoLisp}}==

(let Sieve (range 1 N)

(set Sieve)

===Alternate Version Using a 2x3x5x7 Wheel===

This works by destructively modifying the CDR of the previous cell when it finds a composite number. For sieving large sets (e.g. 1,000,000) it's much faster than the above.

(setq WHEEL-2357

(2 4 2 4 6 2 6 4

 

=={{header|PL/I}}==

 

dcl i fixed bin (31);

 

=={{header|PL/M}}==

 

DECLARE PRIME$MAX LITERALLY '5000';

 

=={{header|PL/SQL}}==

type array_of_booleans is varray(100000000) of boolean;

type table_of_integers is table of integer;

Usage:

 

from table(sieve_of_eratosthenes.find_primes(30));

 

 

=={{header|Pony}}==

use "collections"

 

It is a waste not to do the trivial changes to the above code to sieve odds-only, which is about two and a half times faster due to the decreased number of culling operations; it doesn't really do much about the huge array problem though, other than to reduce it by a factor of two.

 

use "collections"

 

===Basic procedure===

It outputs immediately so that the number can be used by the pipeline.

{

$isprime = @{}

}</syntaxhighlight>

===Another implementation===

function eratosthenes ($n) {

if($n -ge 1){

=={{header|Processing}}==

Calculate the primes up to 1000000 with Processing, including a visualisation of the process.

int maxx;

int maxy;

==={{header|Processing Python mode}}===

 

 

i = 2

===Using lists===

====Basic bounded sieve====

sieve(Xs, L).

 

This is actually the Euler's variant of the sieve of Eratosthenes, generating (and thus removing) each multiple only once, though a sub-optimal implementation.

 

 

range(X, X, [X]) :- !.

We can stop early, with massive improvement in complexity (below ~ <i>n^1.5</i> inferences, empirically, vs. the ~ <i>n²</i> of the above, in ''n'' primes produced; showing only the modified predicates):

 

 

sieve(X, [H | T], [H | T]) :- H*H > X, !.

Optimized by stopping early, traditional sieve of Eratosthenes generating multiples by iterated addition.

 

 

range(X, X, [X]) :- !.

====Sift the Two's and Sift the Three's====

Another version, based on Cloksin&Mellish p.175, modified to stop early as well as to work with odds only and use addition in the removing predicate, instead of the <code>mod</code> testing as the original was doing:

primes(N,[2|R]):- ints(3,N,L), sift(N,L,R).

ints(A,B,[A|C]):- A=<B -> D is A+2, ints(D,B,C).

====Basic variant====

 

 

count(N, D, [N|T]):- freeze(T, (N2 is N+D, count(N2, D, T))).

====Optimized by postponed removal====

Showing only changed predicates.

freeze(PS, (primes(BPS), count(3, 1, NS), sieve(NS, BPS, 4, PS))).

 

to record integers that are found to be composite.

 

% that are less than or equal to N

sieve( N, [2|Rest]) :-

The above has been tested with SWI-Prolog and gprolog.

 

 

?- time( (sieve(100000,P), length(P,N), writeln(N), last(P, LP), writeln(LP) )).

[http://ideone.com/WDC7z Works with SWI-Prolog].

 

retractall(mult(_)),

sieve_O(3,N,PS).

Running it produces

 

[9592, 99991]

[78498, 999983]

Uses a ariority queue, from the paper "The Genuine Sieve of Eratosthenes" by Melissa O'Neill. Works with YAP (Yet Another Prolog)

 

 

prime(2).

 

===Basic procedure===

If Nums(n)=0

m=n*n

 

===Working example===

Define l, n, m, lim

 

avoids explicit iteration in the interpreter, giving a further speed improvement.

 

multiples = set()

for i in range(2, n+1):

===Using array lookup===

The version below uses array lookup to test for primality. The function <tt>primes_upto()</tt> is a straightforward implementation of [http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm Sieve of Eratosthenes]algorithm. It returns prime numbers less than or equal to <tt>limit</tt>.

is_prime = [False] * 2 + [True] * (limit - 1)

for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``

===Using generator===

The following code may be slightly slower than using the array/list as above, but uses no memory for output:

is_prime = [False] * 2 + [True] * (limit - 1)

for n in xrange(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``

is_prime[i] = False

for i in xrange(limit + 1):

[2, 3, 5, 7, 11, 13]</syntaxhighlight>

 

===Odds-only version of the array sieve above===

The following code is faster than the above array version using only odd composite operations (for a factor of over two) and because it has been optimized to use slice operations for composite number culling to avoid extra work by the interpreter:

if limit < 2: return []

if limit < 3: return [2]

The following code is faster than the above generator version using only odd composite operations (for a factor of over two) and because it has been optimized to use slice operations for composite number culling to avoid extra work by the interpreter:

 

yield 2

if limit < 3: return

This uses a 235 factorial wheel for further reductions in operations; the same techniques can be applied to the array version as well; it runs slightly faster and uses slightly less memory as compared to the odds-only algorithms:

 

yield 2; yield 3; yield 5

if limit < 7: return

{{libheader|NumPy}}

Below code adapted from [http://en.literateprograms.org/Sieve_of_Eratosthenes_(Python,_arrays)#simple_implementation literateprograms.org] using [http://numpy.scipy.org/ numpy]

def primes_upto2(limit):

is_prime = numpy.ones(limit + 1, dtype=numpy.bool)

===Using wheels with numpy===

Version with wheel based optimization:

#

def makepattern(smallprimes):

 

Examples:

array([ 2, 3, 5, ..., 999961, 999979, 999983])

>>> primes_upto3(10**7, smallprimes=(2,3)) # Wall time: '''2.13'''

 

{{works with|Python|2.6+, 3.x}}

 

# generates all prime numbers

The adding of each discovered prime's incremental step info to the mapping should be '''''postponed''''' until the prime's ''square'' is seen amongst the candidate numbers, as it is useless before that point. This drastically reduces the space complexity from <i>O(n)</i> to <i>O(sqrt(n/log(n)))</i>, in ''<code>n</code>'' primes produced, and also lowers the run time complexity quite low ([http://ideone.com/VXep9F this test entry in Python 2.7] and [http://ideone.com/muuS4H this test entry in Python 3.x] shows about <i>~ n^1.08</i> [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth empirical order of growth] which is very close to the theoretical value of <i>O(n log(n) log(log(n)))</i>, in ''<code>n</code>'' primes produced):

{{works with|Python|2.6+, 3.x}}

yield 2; yield 3; yield 5; yield 7;

bps = (p for p in primes()) # separate supply of "base" primes (b.p.)

Although theoretically over three times faster than odds-only, the following code using a 2/3/5/7 wheel is only about 1.5 times faster than the above odds-only code due to the extra overheads in code complexity. The [http://ideone.com/LFaRnT test link for Python 2.7] and [http://ideone.com/ZAY0T2 test link for Python 3.x] show about the same empirical order of growth as the odds-only implementation above once the range grows enough so the dict operations become amortized to a constant factor.

{{works with|Python|2.6+, 3.x}}

for p in [2,3,5,7]: yield p # base wheel primes

gaps1 = [ 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8 ]

 

Further gains of about 1.5 times in speed can be made using the same code by only changing the tables and a few constants for a further constant factor gain of about 1.5 times in speed by using a 2/3/5/7/11/13/17 wheel (with the gaps list 92160 elements long) computed for a slight constant overhead time as per the [http://ideone.com/4Ld26g test link for Python 2.7] and [http://ideone.com/72Dmyt test link for Python 3.x]. Further wheel factorization will not really be worth it as the gains will be small (if any and not losses) and the gaps table huge - it is already too big for efficient use by 32-bit Python 3 and the wheel should likely be stopped at 13:

whlPrms = [2,3,5,7,11,13,17] # base wheel primes

for p in whlPrms: yield p

 

=={{header|Quackery}}==

[ 2dup > while

+ 1 >>

 

=={{header|R}}==

if (n < 2) integer(0)

else {

'''Alternate Odds-Only Version'''

 

if (n < 2) return(integer(0))

lmt <- (sqrt(n) - 1) / 2

===Imperative versions===

Ugly imperative version:

 

(define (sieve n)

 

A little nicer, but still imperative:

(define (sieve n)

(define primes (make-vector (add1 n) #t))

 

Imperative version using a bit vector:

(require data/bit-vector)

;; Returns a list of prime numbers up to natural number limit

These examples use infinite lists (streams) to implement the sieve of Eratosthenes in a functional way, and producing all prime numbers. The following functions are used as a prefix for pieces of code that follow:

 

(define (ints-from i d) (cons i (ints-from (+ i d) d)))

(define (after n l f)

==== Basic sieve ====

 

(define x (car l))

(cons x (sieve (diff (cdr l) (ints-from (+ x x) x)))))

Note that the first number, 2, and its multiples stream <code>(ints-from 4 2)</code> are handled separately to ensure that the non-primes list is never empty, which simplifies the code for <code>union</code> which assumes non-empty infinite lists.

 

(let ([x (car l)] [np (car non-primes)])

(cond [(= x np) (sieve (cdr l) (cdr non-primes))] ; else x < np

==== Basic sieve Optimized with postponed processing ====

Since a prime's multiples that count start from its square, we should only start removing them when we reach that square.

(define p (car prs))

(define q (* p p))

Since prime's multiples that matter start from its square, we should only add them when we reach that square.

 

(after q l

(λ(t)

Appears in [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf M.O'Neill's paper]. Achieves on its own the proper postponement that is specifically arranged for in the version above (with <code>after</code>), and is yet more efficient, because it folds to the right and so builds the right-leaning structure of merges at run time, where the more frequently-producing streams of multiples appear <i>higher</i> in that structure, so the composite numbers produced by them have less <code>merge</code> nodes to percolate through:

 

(cons 2 (diff (ints-from 3 1)

(foldr (λ(p r) (define q (* p p))

Same algorithm as [[#With merged composites|"merged composites" above]] (without the postponement optimization), but now using threads and channels to produce a channel of all prime numbers (similar to newsqueak). The macro at the top is a convenient wrapper around definitions of channels using a thread that feeds them.

 

(define-syntax (define-thread-loop stx)

(syntax-case stx ()

Yet another variation of the same algorithm as above, this time using generators.

 

(require racket/generator)

(define (ints-from i d)

(formerly Perl 6)

 

my @is-prime = False, False, slip True xx $limit - 1;

 

 

More or less the same as the first Python example:

# Requires n(1 - 1/(log(n-1))) storage

my $multiples = set();

''Note: while this is "incorrect" by a strict interpretation of the rules, it is being left as an interesting example''

 

gather {

# create an iterator from 2 to $n (inclusive)

 

=={{header|RATFOR}}==

 

program prime

 

=={{header|Red}}==

primes: function [n [integer!]][

poke prim: make bitset! n 1 true

As the stemmed array gets heavily populated, the number of entries ''may'' slow down the REXX interpreter substantially,

<br>depending upon the efficacy of the hashing technique being used for REXX variables (setting/retrieving).

parse arg H .; if H=='' | H=="," then H= 200 /*optain optional argument from the CL.*/

w= length(H); @prime= right('prime', 20) /*W: is used for aligning the output.*/

 

Also added is a final message indicating the number of primes found.

parse arg H .; if H=='' then H=200 /*let the highest number be specified. */

tell=h>0; H=abs(H); w=length(H) /*a negative H suppresses prime listing*/

 

It also uses a short-circuit test for striking out composites &nbsp; ≤ &nbsp; &radic;{{overline|&nbsp;target&nbsp;}}

parse arg H .; if H=='' | H=="," then H= 200 /*obtain the optional argument from CL.*/

w= length(H); @prime= right('prime', 20) /*w: is used for aligning the output. */

 

===Wheel Version restructured===

* 21.07.2012 Walter Pachl derived from above Rexx version

* avoid symbols @ and # (not supported by ooRexx)

 

=={{header|Ring}}==

limit = 100

sieve = list(limit)

=={{header|Ruby}}==

''eratosthenes'' starts with <code>nums = [nil, nil, 2, 3, 4, 5, ..., n]</code>, then marks (　the nil setting　) multiples of <code>2, 3, 5, 7, ...</code> there, then returns all non-nil numbers which are the primes.

nums = [nil, nil, *2..n]

(2..Math.sqrt(n)).each do |i|

* Both inner loops skip multiples of 2 and 3.

 

# For odd i, if i is prime, nums[i >> 1] is true.

# Set false for all multiples of 3.

This simple benchmark compares ''eratosthenes'' with ''eratosthenes2''.

 

Benchmark.bmbm {|x|

x.report("eratosthenes") { eratosthenes(1_000_000) }

[[MRI]] 1.9.x implements the sieve of Eratosthenes at file [http://redmine.ruby-lang.org/projects/ruby-19/repository/entry/lib/prime.rb prime.rb], <code>class EratosthensesSeive</code> (around [http://redmine.ruby-lang.org/projects/ruby-19/repository/entry/lib/prime.rb#L421 line 421]). This implementation optimizes for space, by packing the booleans into 16-bit integers. It also hardcodes all primes less than 256.

 

p Prime::EratosthenesGenerator.new.take_while {|i| i <= 100}</syntaxhighlight>

 

=={{header|Run BASIC}}==

dim flags(limit)

for i = 2 to limit

A slightly more idiomatic, optimized and modern iterator output example.

 

const START: usize = 2;

if n < START {

 

===Sieve of Eratosthenes - No optimization===

 

let mut is_prime = vec![true; limit+1];

The above code doesn't even do the basic optimizing of only culling composites by primes up to the square root of the range as allowed in the task; it also outputs a vector of resulting primes, which consumes memory. The following code fixes both of those, outputting the results as an Iterator:

 

use std::time::Instant;

 

The following code improves the above code by sieving only odd composite numbers as 2 is the only even prime for a reduction in number of operations by a factor of about two and a half with reduction of memory use by a factor of two, and bit-packs the composite sieving array for a further reduction of memory use by a factor of eight and with some saving in time due to better CPU cache use for a given sieving range; it also demonstrates how to eliminate the redundant array bounds check:

 

if limit < 3 {

return if limit < 2 { Box::new(empty()) } else { Box::new(once(2)) }

While that above code is quite fast, as the range increases above the 10's of millions it begins to lose efficiency due to loss of CPU cache associativity as the size of the one-large-array used for culling composites grows beyond the limits of the various CPU caches. Accordingly the following page-segmented code where each culling page can be limited to not larger than the L1 CPU cache is about four times faster than the above for the range of one billion:

 

use std::rc::Rc;

use std::cell::RefCell;

 

=={{header|S-BASIC}}==

comment

Find primes up to the specified limit (here 1,000) using

The following defines an IML routine to compute the sieve, and as an example stores the primes below 1000 in a dataset.

 

start sieve(n);

a = J(n,1);

{{incorrect|SASL|These use REM (division) testing and so are Trial Division algorithms, not Sieve of Eratosthenes.}}

Copied from SASL manual, top of page 36. This provides an infinite list.

show primes

WHERE

 

The limited list for the first 1000 numbers

show primes

WHERE

 

=== Genuine Eratosthenes sieve===

import scala.collection.parallel.mutable

import scala.compat.Platform

The following [['''odds-only''']] code is written in a very concise functional style (no mutable state other than the contents of the composites buffer and "higher order functions" for clarity), in this case using a Scala mutable BitSet:

 

def makeSoE_PrimesTo(top: Int): Iterator[Int] = {

val topNdx = (top - 3) / 2 //odds composite BitSet buffer offset down to 3

The below [['''odds-only''']] code using a primitive array (bit packed) and tail recursion to avoid some of the enumeration delays due to nested complex "higher order" function calls is almost eight times faster than the above more functional code:

 

def makeSoE_PrimesTo(top: Int) = {

import scala.annotation.tailrec

It can be tested with the following code:

 

import SoEwithArray._

val top_num = 100000000

The above code still uses an amount of memory proportional to the range of the sieve (although bit-packed as 8 values per byte). As well as only sieving odd candidates, the following code uses a fixed range buffer that is about the size of the CPU L2 cache plus only storage for the base primes up to the square root of the range for a large potential saving in RAM memory used as well as greatly reducing memory access times. The use of innermost tail recursive loops for critical loops where the majority of the execution time is spent rather than "higher order" functions from iterators also greatly reduces execution time, with much of the remaining time used just to enumerate the primes output:

 

import scala.annotation.tailrec

As the above and all following sieves are "infinite", they all require an extra range limiting condition to produce a finite output, such as the addition of ".takeWhile(_ <= topLimit)" where "topLimit" is the specified range as is done in the following code:

 

import APFSoEPagedOdds._

countSoEPrimesTo(100)

The following code uses delayed recursion via Streams to implement the Richard Bird algorithm mentioned in the last part (the Epilogue) of [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf M.O'Neill's paper], which is '''a true incremental Sieve of Eratosthenes'''. It is nowhere near as fast as the array based solutions due to the overhead of functionally chasing the merging of the prime multiple streams; this also means that the empirical performance is not according to the usual Sieve of Eratosthenes approximations due to this overhead increasing as the log of the sieved range, but it is much better than [[Primality_by_trial_division#Odds-Only_.22infinite.22_primes_generator_using_Streams_and_Co-Inductive_Streams|the "unfaithful" sieve]].

 

def oddPrimes: Stream[Int] = {

def merge(xs: Stream[Int], ys: Stream[Int]): Stream[Int] = {

}</syntaxhighlight>

 

 

def primesBirdCIS: Iterator[Int] = {

As per [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf the "unfaithful sieve" article linked above], the incremental "infinite" Sieve of Eratosthenes can be implemented using a hash table instead of a Priority Queue or Map (Binary Heap) as were used in that article. The following implementation postpones the adding of base prime representations to the hash table until necessary to keep the hash table small:

 

val nextComposites = scala.collection.mutable.HashMap[Int, Int]()

def oddPrimes: Iterator[Int] = {

===Tail-recursive solution===

{{Works with|Scheme|R<math>^5</math>RS}}

(define (sieve n)

(define (aux u v)

 

===Simpler, non-tail-recursive solution===

(define (iota start stop stride)

(if (> start stop)

(newline)</syntaxhighlight>

Output:

===Optimised using an odds-wheel===

Optimised using a pre-computed wheel based on 2 (i.e. odds only):

(let ((stop (sqrt limit)))

(define (sieve lst)

(newline)</syntaxhighlight>

Output:

 

===Vector-based===

Vector-based (faster), works with R<math>^5</math>RS:

(define (initialize! v)

(define (iter v n) (if (>= n (vector-length v))

Using SICP-style ''head''-forced streams. Works with MIT-Scheme, Chez Scheme, &ndash; or any other Scheme, if writing out by hand the expansion of the only macro here, <code>s-cons</code>, with explicit lambda. Common functions:

 

(define (head s) (car s))

(define (tail s) ((cdr s)))

====The simplest, naive sieve====

Very slow, running at ~ <i>n^2.2</i>, empirically, and worsening:

(let ((p (head s)))

(s-cons p

Stops at the square root of the upper limit ''m'', running at about ~ <i>n^1.4</i> in ''n'' primes produced, empirically. Returns infinite stream

of numbers which is only valid up to ''m'', includes composites above it:

(define (sieve s)

(let ((p (head s)))

====Combined multiples sieve====

Archetypal, straightforward approach by Richard Bird, presented in [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf Melissa E. O'Neill article]. Uses <code>s-linear-join</code>, i.e. right fold, which is less efficient and of worse time complexity than the ''tree''-folding that follows. Does not attempt to conserve space by arranging for the additional inner feedback loop, as is done in the tree-folding variant below.

(define (mults p) (from-By (* p p) p))

(define primes ;; primes are

Here is a version of the same sieve, which is self contained with all the requisite functions wrapped in the overall function; optimized further. It works with odd primes only, and arranges for a separate primes feed for the base primes separate from the output stream, ''calculated recursively'' by the recursive call to "oddprms" in forming "cmpsts". It also ''"fuses"'' two functions, <code>s-diff</code> and <code>from-By</code>, into one, <code>minusstrtat</code>:

 

(define (mltpls p)

(define pm2 (* p 2))

It can be tested with the following code:

 

(let nxtprm ((cnt 0) (ps (birdPrimes)))

(if (< cnt n) (nxtprm (+ cnt 1) ((cdr ps))) (car ps))))

The most efficient. Finds composites as a tree of unions of each prime's multiples.

 

;;;; runs in ~ n^1.15 run time in producing n = 100K .. 1M primes

(define (primes-stream)

This can be also accomplished by the following self contained code which follows the format of the <code>birdPrimes</code> code above with the added "pairs" function integrated into the "mrgmltpls" function:

 

(define (mltpls p)

(define pm2 (* p 2))

===Generators===

 

(lambda ()

(let ((ans n))

 

=={{header|Scilab}}==

a = ~zeros(n, 1)

a(1) = %f

 

=={{header|Scratch}}==

when clicked

broadcast: fill list with zero (0) and wait

=={{header|Seed7}}==

The program below computes the number of primes between 1 and 10000000:

 

const func set of integer: eratosthenes (in integer: n) is func

=={{header|Sidef}}==

{{trans|Raku}}

var sieve_arr = [false, false, (limit-1).of(true)...]

gather {

 

Alternative implementation:

var composite = []

for n in (2 .. limit.isqrt) {

=={{header|Simula}}==

{{works with|Simula-67}}

INTEGER ARRAY t(0:1000);

INTEGER i,j,k;

997</pre>

===A Concurrent Prime Sieve===

! A CONCURRENT PRIME SIEVE ;

 

=={{header|Smalltalk}}==

A simple implementation that you can run in a workspace. It finds all the prime numbers up to and including <i>limit</i>—for the sake of example, up to and including 100.

limit := 100.

potentialPrimes := Array new: limit.

Using strings instead of arrays, and the square/sqrt optimizations.

 

sieve i = lt(i,n - 1) i + 1 :f(sv1)

str = str (i + 1) ' ' :(sieve)

=={{header|Standard ML}}==

Works with SML/NJ. This uses BitArrays which are available in SML/NJ. The algorithm is the one on wikipedia, referred to above. Limit: Memory, normally. When more than 20 petabyte of memory available, this code will have its limitation at a maximum integer around 1.44*10E17, due to the maximum list length in SMLNJ. Using two extra loops, however, bit arrays can simply be stored to disk and processed in multiple lists. With a tail recursive wrapper function as well, the upper limit will be determined by available disk space only.

val segmentedSieve = fn N =>

(* output : list of {segment=bit segment, start=number at startposition segment} *)

</syntaxhighlight>

Example, segment size 120 million, prime numbers up to 2.5 billion:

-val writeSegment = fn L : {segment:BitArray.array, start:IntInf.int} list => fn NthSegment =>

let

=={{header|Stata}}==

A program to create a dataset with a variable p containing primes up to a given number.

args n

clear

 

Example call

list in 1/10 // show only the first ten primes

 

=== Mata ===

 

real colvector sieve(real scalar n) {

real colvector a

 

=={{header|Swift}}==

 

let max = 1_000_000

 

The most obvious two improvements are to sieve for only odds as two is the only even prime and to make the sieving array bit-packed so that instead of a whole 8-bit byte per number representation there, each is represented by just one bit; these two changes improved memory use by a factor of 16 and the better CPU cache locality more than compensates for the extra code required to implement bit packing as per the following code:

LazyMapSequence<UnfoldSequence<Int, (Int?, Bool)>, Int> {

 

To use Swift's "higher order functions" on the generated `Sequence`'s effectively, one needs unbounded (or only by the numeric range chosen for the implementation) sieves. Many of these are incremental sieves that, instead of buffering a series of culled arrays, records the culling structure of the culling base primes (which should be a secondary stream of primes for efficiency) and produces the primes incrementally through reference and update of that structure. Various structures may be chosen for this, as in a MinHeap Priority Queue, a Hash Dictionary, or a simple List tree structure as used in the following code:

 

func soeTreeFoldingOdds() -> UnfoldSequence<Int, (Int?, Bool)> {

 

As the above code is slow due to memory allocations/de-allocations and the inherent extra "log n" term in the complexity, the following code uses a Hash Dictionary which has an average of O(1) access time (without the "log n" and uses mutability for increased seed so is in no way purely functional:

var bp = 5; var q = 25

var bps: UnfoldSequence<Int, Int>.Iterator? = nil

 

An unbounded array-based algorithm can be written that combines the excellent cache locality of the second bounded version above but is unbounded by producing a sequence of sieved bit-packed arrays that are CPU cache size as required with a secondary stream of base primes used in culling produced in the same fashion, as in the following code:

 

typealias Prime = UInt64

 

=={{header|Tailspin}}==

templates sieve

def limit: $;

 

Better version using the mutability of the @-state to just update a primality flag

templates sieve

def limit: $;

 

=={{header|Tcl}}==

 

proc sieve n {

 

=={{header|TI-83 BASIC}}==

N→Dim(L1)

For(I,2,N)

{{works with|Korn Shell}}

{{works with|Zsh}}

typeset -a a

typeset i j

 

{{works with|Bourne Shell}}

 

LIMIT=1000

 

{{works with|Bourne Shell}}

seq 2 1000

}

 

{{works with|Bourne Shell}}

fill () {

# This pipeline would begin

==={{header|C Shell}}===

{{trans|CMake}}

@ limit = 80

 

{{incorrect|Ursala|It probably (remainder) uses rem testing and so is a trial division algorithm, not a sieve of Eratosthenes.}}

with no optimizations

 

sieve = ~<{0,1}&& iota; @NttPX ~&r->lx ^/~&rhPlC remainder@rlX~|@r</syntaxhighlight>

test program:

 

example = sieve 50</syntaxhighlight>{{out}}

=={{header|Vala}}==

{{libheader|Gee}}Without any optimizations:

 

ArrayList<int> primes(int limit){

 

=={{header|VAX Assembly}}==

0000 0000 2 .entry main,0

7E 7CFD 0002 3 clro -(sp) ;result buffer

 

=={{header|VBA}}==

'BRRJPA

'Prime calculation for VBA_Excel

=={{header|VBScript}}==

To run in console mode with cscript.

Dim sieve()

If WScript.Arguments.Count>=1 Then

=={{header|Visual Basic}}==

'''Works with:''' VB6

Dim sieve() As Boolean

Dim n As Integer, i As Integer, j As Integer

 

=={{header|Visual Basic .NET}}==

Console.WriteLine("Enter number to search to: ")

limit = Console.ReadLine

===Alternate===

Since the sieves are being removed only above the current iteration, the separate loop for display is unnecessary. And no '''Math.Sqrt()''' needed. Also, input is from command line parameter instead of Console.ReadLine(). Consolidated ''If'' block with ''For'' statement into two ''Do'' loops.

Sub Main(args() As String)

Dim lmt As Integer = 500, n As Integer = 2, k As Integer

{{trans|go}}

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

limit := 201 // means sieve numbers < 201

 

=={{header|Vorpal}}==

p = new()

p.fill(0, m, 1, true)

=={{header|Xojo}}==

Place the following in the '''Run''' event handler of a Console application:

Dim s As String

Dim t As Double

This version uses a dynamic array and can use (a lot) less memory. It's (a lot) slower too.

Since Booleans are manually set to True, the algorithm makes more sense.

Dim s As String

Dim t As Double

=={{header|Woma}}==

 

i<@>range(n*n, limit+1, n)

is_prime = is_prime[$]i,False

 

=={{header|Wren}}==

if (n < 2) return []

var comp = List.filled(n-1, false)

 

=={{header|XPL0}}==

int Size, Prime, I, Kill;

char Flag;

 

=={{header|Yabasic}}==

 

// ---------------------------

 

=={{header|Zig}}==

const std = @import("std");

const stdout = std.io.getStdOut().outStream();

{{trans|BCPL}}

Includes the iterator, as with the BCPL Odds-only bit packed sieve. Since it's not much extra code, the sieve object also includes methods for getting the size and testing for membership.

const std = @import("std");

const heap = std.heap;

</pre>

===Optimized version===

const stdout = @import("std").io.getStdOut().writer();

 

 

=={{header|zkl}}==

composite:=Data(limit+1).fill(1); // bucket of bytes set to 1 (prime)

(2).pump(limit.toFloat().sqrt()+1, Void, // Void==no results, just loop