Lots of Atkin and some Erat

atkin.clj

(set! *warn-on-reflection* true)

(defn atkin [^booleans buffer]
  (let [end (int (alength buffer))
        limit (int (Math/ceil (Math/sqrt end)))]
    (loop [x (int 1)]
      (let [x2 (int (* x x))
            x2_3 (int (* x2 3))]
        (loop [y (int 1)]
          (let [y2 (int (* y y))
                n1 (int (+ (* 4 x2) y2))
                n2 (+ x2_3 y2)
                n3 (- x2_3 y2)]
            (when (and (< n1 end) (or (= (mod n1 12) 1) (= (mod n1 12) 5)))
              (aset buffer n1 (not (aget buffer n1))))
            (when (and (< n2 end) (= (mod n2 12) 7))
              (aset buffer n2 (not (aget buffer n2))))
            (when (and (> x y) (< n3 end) (= (mod n3 12) 11))
              (aset buffer n3 (not (aget buffer n3)))))
          (if (< y limit) (recur (inc y))))
        (if (< x limit) (recur (inc x)))))
    (loop [n (int 5)]
      (let [k (int (* n n))]
        (when (aget buffer n)
          (doseq [i (iterate #(+ 2 %) 1) :let [m (* i k)]
                :while (< m end)]
            (aset buffer m false))))
      (if (<= n limit) (recur (int (+ n 2)))))
    (aset buffer 2 true)
    (aset buffer 3 true)))


(defn print-numbers [buffer]
  (let [indexed-buffer (map vector (iterate inc 0) buffer)]
    (doseq [[i v] indexed-buffer
            :when v]
      (println i))))

(defn count-primes [buffer]
  (reduce + (for [bit buffer :when bit] 1)))


(let [buffer (boolean-array 10000000)]
  (time (atkin buffer))
  ;(print-numbers buffer)
  ;(println (count-primes buffer)))
)

atkin.js

Array.dim = function(dimension, initial) {
    var a = [], i;
    for(i = 0; i < dimension; i+=1) {
        a[i] = initial;
    }
    return a;
}

var atkin = function(buffer) {
    var end = buffer.length;
    var limit = Math.sqrt(end);
    var n, x, x2, x2_3, y, y2;
    var k, i, m;

    for(x = 1; x <= limit; ++x) {
        x2 = x * x;
        x2_3 = 3 * x2;

        for(y = 1; y <= limit; ++y) {
            y2 = y*y;
            n = 4 * x2 + y2;
            if((n < end) && (n % 12 == 1 || n % 12 == 5)) {
                buffer[n] = ~buffer[n];
            }

            n = x2_3 + y2; /* 3x^2 + y^2 */
            if((n < end) && (n % 12 == 7)) {
                buffer[n] = ~buffer[n];
            }

            n = x2_3 - y2; /* 3x^2 - y^2 */
            if((x > y) && (n < end) && (n % 12 == 11)) {
                buffer[n] = ~buffer[n];
            }
        }
    }

    for(n = 5; n <= limit; n+=2) {
        if(buffer[n]) {
            k = n * n;
            for(i = 1, m = k; m < end; i+=2, m = i * k) {
                buffer[m] = false;
            }
        }
    }

    buffer[3] = true;
    buffer[2] = true;
}

var printAll = function(buffer) {
    var i;
    for(i =0; i < buffer.length; ++i) {
        if(buffer[i]) {
            console.log("%d, ", i);
        }
    }
}

var countAll = function(buffer) {
    var i, counter;
    counter = 0;
    for(i =0; i < buffer.length; ++i) {
        if(buffer[i]) {
            counter += 1;
        }
    }
    return counter;
}

var defaultSize = 1000;
var size = defaultSize;
var sizeString = process.argv[2];

if(sizeString !== undefined) {
    size = parseInt(sizeString);
    size = (size === NaN) ? defaultSize : size;
}

var buffer = Array.dim(size, false);
console.time('atkin');
atkin(buffer);
console.timeEnd('atkin');
console.log("%d\n", countAll(buffer));

atkin_f.py

def atkin(buffer, end):
    limit = int(math.ceil(math.sqrt(end)))
    
    for x in range(1, limit + 1):
        x2 = x * x
        x2_3 = 3 * x2

        for y in range(1, limit + 1):
            y2 = y * y

            n = 4 * x2 + y2
            if (n < end) and (n % 12 == 1 or n % 12 == 5):
                buffer[n] = not buffer[n]

            n = x2_3 + y2
            if (n < end) and (n % 12 == 7):
                buffer[n] = not buffer[n]

            n = x2_3 - y2
            if (x > y) and (n < end) and (n % 12 == 11):
                buffer[n] = not buffer[n]

    for n in range(5, limit+1):
        if buffer[n]:
            k = n * n
            m = k
            i = 1
            
            while m < end:
                buffer[m] = False
                i += 2
                m = i * k

    buffer[2] = True
    buffer[3] = True
    return buffer

atkin_main.py

try:
    import numpy as np
    def create_buffer(size):
        arr = np.zeros(size+1, dtype=np.bool)
        return arr, arr.size
except ImportError:
    def create_buffer(size):
        arr = [False, ] * (size+1)
        return arr, len(arr)

# ...

def main(args):
    max_integer = parse_args(args)
    buffer, upper_bound = create_buffer(max_integer)
    atkin(buffer, upper_bound)

AtkinSieveArray.java

import java.lang.Boolean;
import java.lang.Integer;

public class AtkinSieveArray {

    static private int count(boolean[] buffer) {
        int counter = 0;
        for(int i = 2; i < buffer.length; ++i) {
            if(buffer[i]) {
                counter++;
            }
        }
        return counter;
    }
    
    static private void sieve(boolean[] buffer) {
        int end = buffer.length;
        double limit = Math.sqrt(end);

        int n, x, x2, x2_3, y, y2;
        int k, i, m;

        for (x = 1; x <= limit; ++x) {
            x2 = x * x;
            x2_3 = 3 * x2;

            for (y = 1; y <= limit; ++y) {
                y2 = y * y;
                n = 4 * x2 + y2;
                if ((n < end) && (n % 12 == 1 || n % 12 == 5)) {
                    buffer[n] = !buffer[n];
                }

                n = x2_3 + y2; /* 3x^2 + y^2 */
                if ((n < end) && (n % 12 == 7)) {
                    buffer[n] = !buffer[n];
                }

                n = x2_3 - y2; /* 3x^2 - y^2 */
                if ((x > y) && (n < end) && (n % 12 == 11)) {
                    buffer[n] = !buffer[n];
                }
            }
        }

        for (n = 5; n <= limit; n += 2) {
            if (buffer[n]) {
                k = n * n;
                for (i = 1, m = k; m < end; i += 2, m = i * k) {
                    buffer[m] = false;
                }
            }
        }

        buffer[3] = true;
        buffer[2] = true;
    }

    public static void main(String[] args) {
        int max;
        boolean buffer[] = null;

        if (args.length > 0) {
            max = Integer.valueOf(args[0]);
        } else {
            max = 1000;
        }

        buffer = new boolean[max+1];

        long start = System.currentTimeMillis();
        sieve(buffer);

        System.out.println(count(buffer));
        System.out.println(System.currentTimeMillis() - start);


    }

}

erat.py

def init_small_primes(end):
    limit = int(math.ceil(math.sqrt(end)))
    buffer = np.ones(end, dtype=np.bool)
    buffer[0] = buffer[1] = 0
    for i in xrange(2, limit):
        if buffer[i]:
            buffer[np.arange(2*i, end, step=i)] = 0
    return np.nonzero(buffer)[0]

def erat(buffer, end, small_primes=[2, 3, 5, 7]):
    limit = int(math.ceil(math.sqrt(end)))
    buffer[0] = buffer[1] = 0

    for p in small_primes:
        buffer[np.arange(p*p, end, step=p)] = 0

    for i in xrange(p+1, limit):
        if buffer[i]:
            buffer[np.arange(2*i, end, step=i)] = 0


def main(args):
    max_integer, small_primes_end = parse_args(args)
    small_primes = init_small_primes(small_primes_end)
    buffer, upper_bound = create_buffer(max_integer)
    erat(buffer, upper_bound, small_primes)

    print np.nonzero(buffer)

erat_basic.py

def erat_basic(buffer, end):
    limit = int(math.ceil(math.sqrt(end)))
    buffer[0] = buffer[1] = 0
    for i in xrange(2, limit):
        if buffer[i]:
            buffer[np.arange(2*i, end, step=i)] = 0

erat_unroll.py

def erat_unroll(buffer, end):
    limit = int(math.ceil(math.sqrt(end)))
    buffer[0] = buffer[1] = 0
    buffer[np.arange(4, end, step=2)] = 0
    buffer[np.arange(9, end, step=3)] = 0
    buffer[np.arange(25, end, step=5)] = 0
    buffer[np.arange(49, end, step=7)] = 0
    buffer[np.arange(121, end, step=11)] = 0
    buffer[np.arange(169, end, step=13)] = 0
    buffer[np.arange(289, end, step=17)] = 0
    buffer[np.arange(361, end, step=19)] = 0
    for i in xrange(23, limit):
        if buffer[i]:
            buffer[np.arange(2*i, end, step=i)] = 0