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

Question

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

Введение

Я написал этот причудливый маленький метод, который генерирует массив 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;
}

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

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

Answer 5

Самым простым решением было бы вернуть какой-нибудь член Структура коллекций вместо массива.

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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 10

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

Answer 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's 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;
}

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

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

Answer 13

Я использовал HashMap и нашел это очень простым

import java.util.HashMap;
import java.util.Map;

/*Using Algorithms such as sieve of Eratosthanas */

public class PrimeNumber {

    public static void main(String[] args) {

        int prime = 15;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        hashMap.put(0, 0);
        hashMap.put(1, 0);
        for (int i = 2; i <= prime; i++) {

            hashMap.put(i, 1);// Assuming all numbers are prime
        }

        printPrimeNumberEratoshanas(hashMap, prime);

    }

    private static void printPrimeNumberEratoshanas(HashMap<Integer, Integer> hashMap, int prime) {

        System.out.println("Printing prime numbers upto" + prime + ".....");
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue().equals(1)) {
                System.out.println(entry.getKey());
                for (int j = entry.getKey(); j < prime; j++) {
                    for (int k = j; k * j <= prime; k++) {
                        hashMap.put(j * k, 0);
                    }
                }

            }
        }

    }

}

Думаете, это эффективно

Answer 14

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