Encontrar números primos com o Crivo de Eratóstenes (Originalmente: Existe uma melhor maneira de preparar essa matriz?)

Question

Nota: Version 2, abaixo, usa o Crivo de Eratóstenes. Há várias respostas que ajudaram com o que eu originalmente solicitado. Eu escolhi o método Crivo de Eratóstenes, implementou, e mudou o título da pergunta e marcas de forma adequada. Obrigado a todos que ajudaram!

Introdução

Eu escrevi este método pouco de fantasia que gera uma matriz de int contendo os números primos menos do que o especificado limite superior. Ele funciona muito bem, mas eu tenho uma preocupação.

O método

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

A minha preocupação

A minha preocupação é que eu estou criando uma matriz que é demasiado grande para o número final de elementos do método retornará. O problema é que eu não sei de uma boa maneira de adivinhar corretamente o número de números primos menos de um número especificado.

Foco

Esta é a forma como o programa usa as matrizes. Isto é o que eu quero melhorar.

1. criar uma matriz temporária que é suficientemente grande para conter todos os números menos do que o limite.
2. I gerar os números primos, enquanto contagem de manutenção de quantas eu tenho gerado.
3. I fazer uma nova matriz que é o direito dimensão à espera apenas o nobre números.
4. I copiar cada número primo do enorme variedade para a matriz do dimensão correta.
5. eu voltar a matriz da correcta dimensão que contém apenas o nobre números que eu gerado.

Perguntas

1. Posso copiar todo o pedaço (de uma vez) de temp[] que tem diferente de zero elementos para primes[] sem ter que percorrer tanto matrizes e copiar os elementos um por um?
2. Existem estruturas de dados que comportar-se como uma matriz de primitivas que pode crescer à medida que os elementos são adicionados, em vez de exigir uma dimensão sobre instanciação? O que é penalidade de desempenho em comparação com usando uma matriz de primitivos?

---

Version 2 (graças a Jon Skeet ):

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

---

Versão 3 (graças a Paul Tomblin ) que utiliza o Peneira de Erastosthenes :

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

Seu método de encontrar números primos, comparando cada elemento da matriz com cada possível fator é terrivelmente ineficiente. Você pode melhorar imensamente fazendo uma Crivo de Eratóstenes todo o conjunto, ao mesmo tempo. Além de fazer muito menos comparações, ele também usa disso, em vez de divisão. Divisão é a maneira mais lenta.

Answer 2

ArrayList<> Crivo de Eratóstenes

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

Fórmula de limite superior do número de números primos menos do que ou igual a max (ver wolfram.com ):

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

Answer 3

Criar um ArrayList<Integer> e depois converter para um int[] no final.

Existem vários 3rd party IntList (etc) aulas ao redor, mas a menos que você está realmente preocupado com o hit de boxe alguns inteiros, eu não me preocuparia com isso.

Você pode usar Arrays.copyOf para criar a nova matriz embora. Você também pode querer redimensionar dobrando de tamanho a cada vez que você precisa para, em seguida, cortar no final. Isso seria basicamente ser imitando o comportamento ArrayList.

Answer 4

Algo usando Crivo de Eratóstenes

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

Imagem que descreve o acima algo (células cor cinza representam número primo. Uma vez que consideramos todos os números como números primos inicialmente, o todo é grade é cinza inicialmente.)

Fonte da imagem: WikiMedia

Answer 5

A solução mais fácil seria para retornar algum membro da Collections Framework vez de uma matriz.

Answer 6

Você está usando Java 1.5? Por que não voltar List<Integer> e uso ArrayList<Integer>? Se você precisa retornar um int[], você pode fazê-lo através da conversão de lista para int[] no final do processamento.

Answer 7

Como Paulo Tomblin aponta, há melhores algoritmos.

Mas consonância com o que você tem, e assumindo um objeto per resultado é muito grande:

Você está sempre apenas acrescentar à matriz. Assim, usar uma matriz relativamente pequena int []. Quando é plena utilização anexar a uma lista e criar uma substituição. No final copiá-lo em uma matriz de tamanho corretamente.

Alternativamente, adivinhar o tamanho da matriz int []. Se ele for muito pequeno, substitua por um int [] com um tamanho de uma fracção maior do que o tamanho actual matriz. A sobrecarga de este desempenho permanecerá proporcional ao tamanho. (Isso foi discutido brevemente em um recente podcast de stackoverflow.)

Answer 8

Agora que você tem uma peneira básica no lugar, nota que a necessidade de loop interior só continuar até temp[i]*temp[i] > prime.

Answer 9

Eu tenho uma implementação muito eficiente:

1. não mantemos os números pares, portanto, reduzir para metade o uso de memória.
2. usamos BitSet, exigindo apenas um bit por número.
3. estimamos que o limite superior para o número de primos no intervalo, assim podemos definir a initialCapacity para a matriz de forma adequada.
4. nós não realizar qualquer tipo de divisão nas alças.

Aqui está o código:

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

reestruturar seu código. Jogue fora a matriz temporária e, em vez da função de gravação que apenas prime-testa um inteiro. Vai ser razoavelmente rápido, desde que você está usando apenas tipos nativos. Então você pode, por exemplo, loop e construir uma lista de números inteiros que são primos, antes de finalmente converter que para uma matriz de retorno.

Answer 11

Eu finalmente terminei o programa É um otimizado peneira

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

Não sei se isso irá suite sua situação, mas você pode dar uma olhada na minha abordagem. Eu usei o meu usando Crivo de Eratóstenes .

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

Comentário adicionado para cada passos que foi ilustrado na wikipedia

Answer 13

Eu tenho feito usando HashMap e achei muito simples

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

            }
        }

    }

}

Pense isto é eficaz

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