Поиск простых чисел с помощью решета Эратосфена (Изначально: есть ли лучший способ подготовить этот массив?)

Question

Примечание: Версия 2, ниже, использует Сито Эратосфена. Есть несколько ответов, которые помогли с тем, что я первоначально спросил. Я выбрал метод Sieve of Eratosthenes, реализовал его и изменил название вопроса и метки соответствующим образом. Спасибо всем, кто помог!

Введение

Я написал этот причудливый маленький метод, который генерирует массив int, содержащий простые числа, меньшие указанной верхней границы. Это работает очень хорошо, но у меня есть проблема.

Метод

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    int [] primes = new int [index];
    while(--index >= 0) {
        primes [index] = temp [index];
    }
    return primes;
}

Моя забота

Меня беспокоит то, что я создаю массив, который слишком велик для конечного числа элементов, которое будет возвращать метод. Проблема в том, что я не знаю, как правильно угадать число простых чисел меньше указанного числа.

Фокус

Так программа использует массивы. Это то, что я хочу улучшить.

1. Я создаю временный массив, который достаточно большой, чтобы вместить каждый номер меньше лимита.
2. Я генерирую простые числа, а ведя подсчет, сколько у меня есть генерируется.
3. Я создаю новый массив, который является правильным измерение, чтобы держать только премьер число.
4. Я копирую каждое простое число из огромный массив к массиву правильный размер.
5. возвращаю массив правильный измерение, которое содержит только простое числа, которые я сгенерировал.

Вопросы

1. Могу ли я скопировать весь кусок (сразу) из temp[] с ненулевым элементы к primes[] без необходимости перебирать оба массива и скопировать элементы один за другим?
2. Существуют ли структуры данных, которые вести себя как массив примитивов которые могут расти при добавлении элементов, вместо того, чтобы требовать измерения на момент создания? Что снижение производительности по сравнению с используя массив примитивов?

---

Версия 2 (спасибо Джону Скиту ):

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    return Arrays.copyOfRange(temp, 0, index);
}

---

Версия 3 (благодаря Полу Томблину ), в котором используется Сито Эрастосфена :

private static int [] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) {
        if (!isComposite [i]) {
            for (int j = i; i * j <= max; j++) {
                isComposite [i*j] = true;
            }
        }
    }
    int numPrimes = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) numPrimes++;
    }
    int [] primes = new int [numPrimes];
    int index = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) primes [index++] = i;
    }
    return primes;
}

Answer 1

Ваш метод поиска простых чисел путем сравнения каждого элемента массива со всеми возможными факторами ужасно неэффективен. Вы можете значительно улучшить его, выполнив Сито Эратосфена сразу по всему массиву. Помимо выполнения гораздо меньшего количества сравнений, он также использует сложение, а не деление. Деление намного медленнее.

Answer 2

ArrayList<> Сито Эратосфена

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

Формула для верхней границы числа простых чисел, меньших или равных max (см. wolfram.com ):

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}

Answer 3

Создайте ArrayList<Integer>, а затем преобразуйте в int[] в конце.

Существуют различные сторонние классы IntList (и т. Д.), Но если вы не действительно обеспокоены попаданием в бокс целых чисел, я бы не стал беспокоиться об этом.

Вы можете использовать Arrays.copyOf для создания нового массива. Вы также можете захотеть изменить размер, удваивая размер каждый раз, когда вам нужно, а затем обрезать в конце. Это в основном имитирует поведение ArrayList.

Answer 4

Алго с использованием сита Эратосфена

public static List<Integer> findPrimes(int limit) {

    List<Integer> list = new ArrayList<>();

    boolean [] isComposite = new boolean [limit + 1]; // limit + 1 because we won't use '0'th index of the array
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= limit; i++) {
        if (!isComposite[i]) {
            // 'i' is a prime number
            list.add(i);
            int multiple = 2;
            while (i * multiple <= limit) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return list;
}

Изображение, изображающее вышеприведенный алгоритм (ячейки серого цвета представляют простое число. Поскольку все числа мы рассматриваем как простые числа изначально, вся сетка изначально является серой.)

Источник изображения: WikiMedia

Answer 5

Вы используете Java 1.5? Почему бы не вернуть List<Integer> и использовать ArrayList<Integer>? Если вам нужно вернуть int[], вы можете сделать это, преобразовав List в int[] в конце обработки.

Answer 6

Самым простым решением было бы вернуть некоторый элемент Collections Framework вместо массива.

Answer 7

У меня действительно эффективная реализация:

1. мы не сохраняем четные числа, поэтому используем память в два раза меньше.
2. мы используем BitSet, требуя только один бит на число.
3. мы оцениваем верхнюю границу для числа простых чисел на интервале, поэтому мы можем соответственно установить initialCapacity для массива.
4. мы не выполняем никакого деления в циклах.

Вот код:

public ArrayList<Integer> sieve(int n) {
    int upperBound = (int) (1.25506 * n / Math.log(n));
    ArrayList<Integer> result = new ArrayList<Integer>(upperBound);
    if (n >= 2)
        result.add(2);

    int size = (n - 1) / 2;
    BitSet bs = new BitSet(size);

    int i = 0;
    while (i < size) {
        int p = 3 + 2 * i;
        result.add(p);

        for (int j = i + p; j < size; j += p)
            bs.set(j);

        i = bs.nextClearBit(i + 1);
    }

    return result;
}

Answer 8

Теперь, когда у вас есть базовое сито, обратите внимание, что внутренняя петля должна продолжаться только до temp[i]*temp[i] > prime.

Answer 9

Как отмечает Пол Томблин, существуют лучшие алгоритмы.

Но придерживаться того, что у вас есть, и предполагать, что объект для результата слишком велик:

Вы только добавляете данные в массив. Итак, используйте относительно небольшой массив int []. Когда он будет полностью использован, добавьте его в список и создайте замену. В конце скопируйте его в массив правильного размера.

Также можно угадать размер массива int []. Если он слишком мал, замените int [] размером, меньшим, чем текущий размер массива. Снижение производительности будет оставаться пропорциональным размеру. (Это было кратко обсуждено в недавнем подкасте stackoverflow.)

Answer 10

public static void primes(int n) {
        boolean[] lista = new boolean[n+1];
        for (int i=2;i<lista.length;i++) {
            if (lista[i]==false) {
                System.out.print(i + " ");
            }
            for (int j=i+i;j<lista.length;j+=i) {
                lista[j]=true;
            }
        }
    }