2

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

Вот мой алгоритм для поиска простых чисел за 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;
}

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

3
  • а почему вы решили что первый за O(n)? если там двойной цикл как минимум.
    – pavel
    1 дек 2019 в 15:01
  • 1
    @pavel во-первых, там не все циклы до N,а только первый. Во-вторых, я оставил ссылку на доказательство в вопрос. Повторю: habr.com/en/post/452388 1 дек 2019 в 15:23
  • А не потому-ли, что ты в первом Integer'ов напихал?
    – Qwertiy
    2 дек 2019 в 8:14

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Посмотрите другие вопросы с метками или задайте свой вопрос.