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

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

Я сделал с помощью 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 2

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

  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 3

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

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 4

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