import java.util.Arrays;

public class Eratosthene{

    public static int[] byteEratosthenes(int cap) {
        int[] result = new int[(int) Math.ceil(1.25 * cap / Math.log(cap))];
        int pos = 1;
        result[0] = 2;
        byte[] primes = new byte[(cap - 2 >> 4) + 1];

        for (int i = 0; i < cap - 2 >> 1; i++) {
            if ((primes[i >> 3] >> (i & 7) & 1) == 0) { // mod => 1 & n^2 for 8086
                result[pos++] = (i * 2 + 3);
                for (long j = 4L * i * i + 12L * i + 9L; j < cap; j += i * 4 + 6) {
                    int number = (int) (j - 3L >> 1);
                    byte mask = (byte) (0b1 << (number & 7));
                    primes[(number >> 3)] |= mask;
                }
            }
        }
        if (result.length > pos) {
            result = Arrays.copyOf(result, pos);
        }
        return result;
    }
}