Поиск простых чисел за O(n)

Есть алгоритм для быстрого поиска простых чисел. Я попытался реализовать его. Вроде работает, но есть проблема. У меня он отрабатывает явно более медленно чем стандартное решето Эратосфена. Не понимаю в чем ошибка.

Вот мой алгоритм для поиска простых чисел за O(n):

public int countPrimes(int n) {
    List<Integer> pr = new ArrayList<>(1000);
    int[] lp = new int[n];
    for (int i = 2; i < n; i++) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.add(i);
        }
        for (int j = 0; j < pr.size(); j++) {
            int p = pr.get(j);
            int updatedIndex = p * i;
            if (updatedIndex < n && updatedIndex > 0 && p <= lp[i]) {
                lp[updatedIndex] = p;
            } else {
                break;
            }
        }
    }
    return pr.size();
}

Вот стандатрный алгоритм через решето Эратосфена:

public int countPrimes(int n) {
    boolean[] flags = getFlags(n);
    int counter = 0;
    for (int i = 0; i < flags.length; i++) {
        if (flags[i]) {
            for (int j = i * i; j < flags.length; j += i) {
                flags[j] = false;
            }
            counter++;
        }
    }
    return counter;
}
private boolean[] getFlags(int n) {
    boolean[] flags = new boolean[n];
    Arrays.fill(flags, true);
    flags[0] = false;
    flags[1] = false;
    return flags;
}

Почему второй работает быстрее первого?