Benchmarks |
|
Eratosthenes |
|
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
|
|