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

Ответ 1

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

Ответ 2

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

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

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

Ответ 3

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;
}

Ответ 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

Ответ 5

Самое простое решение - вернуть некоторую часть Collections Framework вместо массива.

Ответ 6

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

Ответ 7

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

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

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

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

Ответ 8

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

Ответ 9

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

• мы не сохраняем четные числа, поэтому вдвое сокращаем использование памяти.
• мы используем BitSet, требуя только один бит на номер.
• мы оцениваем верхнюю оценку числа простых чисел на интервале, поэтому мы можем соответствующим образом установить initialCapacity для массива.
• мы не выполняем каких-либо делений в циклах.

Здесь код:

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;
}

Ответ 10

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

Ответ 11

Я, наконец, закончил программу Это оптимизированное сито

public static int[] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    LinkedList<Integer> Primes = new LinkedList<>(); //linkedlist so not have to iterate 2 times
    int sqrt = (int) Math.sqrt(max); //end at the square root
    for (int i = 2; i <= sqrt; i++) {
        if (!isComposite[i]) {
            int s = i*i; //start from the prime square
            while (s <= max) {
                isComposite[s] = true; //oh no its a not prime
                s+=i;
            }
        }
    }
    for(int i = 2; i < max; i++){
        if(!isComposite[i]){
            Primes.add(i);
        }
    }
    int[] result = new int[Primes.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = Primes.get(i);
    }
    return result;
}

Ответ 12

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

  public static List<Integer> sieves(int n) {
        Map<Integer,Boolean> numbers = new LinkedHashMap<>();

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

        //First generate a list of integers from 2 to 30
        for(int i=2; i<n;i++){
            numbers.put(i,true);
        }

        for(int i : numbers.keySet()){
            /**
             * The first number in the list is 2; cross out every 2nd number in the list after 2 by 
             * counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):
             * 
             * The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by 
             * counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
             * The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every
             * 7th number in the list after 7, but they are all already crossed out at this point,
             * as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. 
             * The numbers not crossed out at this point in the list are all the prime numbers below 30:
             */
            if(numbers.get(i)){
                for(int j = i+i; j<n; j+=i) {
                    numbers.put(j,false);
                }
            }
        }


        for(int i : numbers.keySet()){
            for(int j = i+i; j<n && numbers.get(i); j+=i) {
                numbers.put(j,false);
            }
        }

        for(int i : numbers.keySet()){
           if(numbers.get(i)) {
               primes.add(i);
           }
        }
        return primes;
    }

Добавлен комментарий для каждого шага, который был проиллюстрирован в wikipedia