Benchmarks
Eratosthenes
 previous   up   next 

The primes between 1 and 10000000 (ten million) should be set in a bitset. To do that the sieve of Eratosthenes should be used. Afterwards the cardinality of the bitset should be computed and written as result.

C++

The C++ template bitset requires that the maximum value is specified at compile time.

#include <bitset>
#include <cstdio>
#include <cmath>

const int maxValueInSet = 10000000;

std::bitset<maxValueInSet + 1> eratosthenes () {
  std::bitset<maxValueInSet + 1> sieve;
  int sqrtN = static_cast<int>(std::sqrt(maxValueInSet));

  sieve.set();
  sieve.reset(0);
  sieve.reset(1);
  for (int i = 2; i <= sqrtN; i++) {
    if (sieve[i]) {
      for (int j = i * i; j <= maxValueInSet; j += i) {
        sieve.reset(j);
      }
    }
  }
  return sieve;
}

int main (int argc, char *argv[]) {
  std::bitset<maxValueInSet + 1> sieve = eratosthenes();
  printf("%d\n", sieve.count());
}

Measurement:

prompt> g++ -O2 sieve.c++ -o sieve
prompt> time ./sieve
664579

real    0m0.037s
user    0m0.037s
sys     0m0.000s

Java

import java.util.BitSet;
import java.lang.String;

public class sieve {

    private static BitSet eratosthenes (int n) {
        BitSet sieve = new BitSet();
        int sqrtN = (int) Math.sqrt(n);

        sieve.set(2, n + 1, true);
        for (int i = 2; i <= sqrtN; i++) {
            if (sieve.get(i)) {
                for (int j = i * i; j <= n; j += i) {
                    sieve.clear(j);
                }
            }
        }
        return sieve;
    }

    public static void main(String args[]) {
        BitSet sieve = eratosthenes(10000000);
        System.out.println(sieve.cardinality());
    }
}

Measurement:

prompt> javac sieve.java
prompt> time java sieve
664579

real    0m0.151s
user    0m0.161s
sys     0m0.019s

JavaScript

It is necessary to install BitSet.js.

const BitSet = require('bitset.js');

function eratosthenes (n) {
    let sieve = new BitSet;
    let sqrtN = Math.trunc(Math.sqrt(n));

    sieve.setRange(2, n);
    for (i = 2; i <= sqrtN; i++) {
        if (sieve.get(i)) {
            for (j = i * i; j <= n; j += i) {
                sieve.clear(j);
            }
        }
    }
    return sieve;
}

(function(){
    let sieve = eratosthenes(10000000);
    console.log(sieve.cardinality());
})();

Measurement:

prompt> time node sieve.js
664579

real    0m0.209s
user    0m0.208s
sys     0m0.004s

Python 3

It is necessary to install bitarray.

from bitarray import bitarray
import math

def eratosthenes(n):
    sieve = bitarray(n + 1)
    sqrtN = math.isqrt(n)

    sieve.setall(1)
    sieve[0] = 0
    sieve[1] = 0
    for i in range(2, sqrtN + 1):
        if sieve[i]:
            for j in range(i ** 2, n + 1, i):
                sieve[j] = 0
    return sieve

def main():
    sieve = eratosthenes(10000000)
    print(sieve.count())

if __name__ == "__main__":
    main()

Measurement:

prompt> time python3 sieve.py
664579

real    0m1.183s
user    0m1.182s
sys     0m0.000s

Seed7

$ include "seed7_05.s7i";

const func set of integer: eratosthenes (in integer: n) is func
  result
    var set of integer: sieve is EMPTY_SET;
  local
    var integer: i is 0;
    var integer: j is 0;
  begin
    sieve := {2 .. n};
    for i range 2 to sqrt(n) do
      if i in sieve then
        for j range i ** 2 to n step i do
          excl(sieve, j);
        end for;
      end if;
    end for;
  end func;

const proc: main is func
  local
    var set of integer: sieve is EMPTY_SET;
  begin
    sieve := eratosthenes(10000000);
    writeln(card(sieve));
  end func;

Measurement:

prompt> s7c -O2 -oc3 sieve
prompt> time ./sieve
664579

real    0m0.037s
user    0m0.037s
sys     0m0.000s

 previous   up   next