Amélioration de l'efficacité du tamis du code d'eratosthène en Java

Question

J'ai travaillé sur un code pour Tamis d'eratosthène En Java, mais je suis confronté à quelques problèmes d'efficacité spatiale. Voici le code:

import java.util.*;

class EratosthenesSeive
{

    public static void main(String args[])
    {

        ArrayList<Long> myPrimeList = new ArrayList<Long>();
        ArrayList<Long> myTempPrimeList = new ArrayList<Long>();
        ArrayList<Boolean> isPrimeNumber = new ArrayList<Boolean>();
        int index = 0;

        long ul = 1500l;
        long ll = 2;

        do
        {
            myTempPrimeList.add(ll);
            isPrimeNumber.add(true);
            ll++;
        }while( ll != (ul+1));

        for(long i : myTempPrimeList)
        {
            if(isPrimeNumber.get(index))
            {
                myPrimeList.add(i);
                for(long j = i ; j*i <= ul; j++)
                {
                    isPrimeNumber.set(myTempPrimeList.indexOf(j*i),false);
                }
            }
            index++;
        }

        System.out.println(myPrimeList);
    }
}

Cela semble fonctionner bien pour la contribution jusqu'à 10 ^ 3, à 10 ^ 4, il est simplement suspendu et à 10 ^ 5 et au-dessus, je reçois OverofMemoryerror. Et le code semble bien fonctionner, mais je voudrais le fixer un peu plus. Aucune suggestion?

Answer 1

Une optimisation possible serait de remplacer les listes de tableau par des tableaux de types primitifs, étant donné que vous connaissez au préalable la taille des tableaux nécessaires. Cela aura pour effet d'empêcher toute la boxe / déballage inutile des valeurs actuellement présentes dans votre code.

Sachez également que vous n'avez pas à stocker des nombres uniformes dans le tableau, seuls des nombres impairs - cela réduira les exigences de mémoire et le temps de traitement de moitié.

Pour résoudre l'OutOfMemoryError, vous pouvez jouer avec les paramètres de configuration de JVM au démarrage, ce qui rend plus d'espace de tas pour l'application.

Answer 2

Vous boxez / débouchez un tonne dans ce code. Vous voudrez peut-être essayer de remplacer le ArrayList<>s avec des tableaux droits du type primitif.

Answer 3

Doublez la vitesse en ne fonctionnant pas avec des nombres pair.

Answer 4

Votre code fait beaucoup plus de travail qu'il en a besoin. Vous avez juste besoin d'une seule gamme de booléens, de deux boucles pour marquer les numéros non prisons et une autre boucle pour imprimer les numéros d'index des nombres premiers. Comme ça:

public void printPrimes(int max) {

    // declare a single array of booleans
    boolean[] primeFlags = new boolean[max + 1];

    // double loop sieve-style and mark non-primes as true
    for (int m = 2; m <= (int)Math.sqrt(max); m++) 
        for (int k = m*m; k <= max; k += m) primeFlags[k] = true;

    // loop over bool array and print indexes with false values 
    // which will be the prime numbers
    for (int m = 2; m <= max; m++)
        if (!primeFlags[m]) System.out.print(m + " ");
}

Answer 5

import java.util.Scanner;

//Sieve Of Erastothenes

public class SieveOfErastothenes {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a range n : ");
        int n = sc.nextInt();

        boolean ar[] = new boolean[n+1];
        for (int i=2;i<=n;i++)
        ar[i] = true;

        for(int i = 2;i*i<=n;i++)
        {
            if(ar[i])
            {
                for(int j=i;i*j<=n;j++)
                    ar[i*j]=false;
            }
        }

        for(int i=2;i<=n;i++)
        {
            if(ar[i])
                System.out.print(i+" ");
        }
        sc.close();

    }

}

/*This code is contributed by Asish Samantaray*/