, 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25

maintenant, regardons ces mêmes nombres, quand nous utilisons le tamis de l'algorithme D'Eratosthène:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

après suppression de 2:

5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25

après suppression de 3:

5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25

c'est le même que le premier set! Remarquez qu'ils comprennent tous les deux 25, ce qui n'est pas premier. Si nous y réfléchissons, c'est un résultat évident. Considérez n'importe quel groupe de 6 nombres consécutifs:

6k - 3, 6k - 2, 6k - 1, 6k, 6k + 1, 6k + 2

Si nous prenons un peu, nous obtenons:

3*(2k-1), 2*(3k - 1), 6k - 1, 6*(k), 6k + 1, 2*(3k + 1)

dans tout groupe de 6 nombres consécutifs, trois d'entre eux seront divisibles par deux, et deux d'entre eux seront divisibles par trois. Ce sont exactement les chiffres que nous avons retiré jusqu'à présent! Par conséquent:

votre algorithme pour utiliser seulement 6k - 1 et 6k + 1 est exactement le même que les deux premiers tours du tamis D'Erathosthène.

c'est une belle amélioration de la vitesse sur le tamis, aussi, parce que nous n'avons pas à ajouter tous ces éléments supplémentaires juste pour les enlever. Cela explique pourquoi votre algorithme fonctionne et pourquoi il ne manque aucun cas; parce que c'est exactement la même chose que le tamis.

---

de toute façon, je suis d'accord qu'une fois que vous avez généré des nombres premiers, votre boolean chemin est de loin le la plus rapide. j'ai mis en place un benchmark en utilisant votre ArrayList chemin, votre boolean[] chemin, et mon propre chemin en utilisant LinkedList et iterator.remove() (parce que les retraits sont rapides dans un LinkedList . Voici le code de mon harnais d'essai. Notez que j'ai effectué le test 12 fois pour s'assurer que le JVM est réchauffé, et j'imprime la taille de la liste et changer la taille de n pour tenter d'empêcher trop prédiction de branche optimisation. Vous pouvez également obtenir plus rapidement dans les trois méthodes, en utilisant += 6 dans la graine initiale, au lieu de prod6k :

import java.util.*;

public class PrimeGenerator {
  public static List<Integer> generatePrimesArrayList(int n) {
    List<Integer> primes = new ArrayList<>(getApproximateSize(n));
    primes.add(2);// explicitly add
    primes.add(3);// 2 and 3

    for (int i = 6; i <= n; i+=6) {
      // get all the numbers which can be generated by the formula
      primes.add(i - 1);
      primes.add(i + 1);
    }

    for (int i = 0; i < primes.size(); i++) {
      int k = primes.get(i);
      // remove all the factors of the numbers generated by the formula
      for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
                                         // to DTing
      {
        int index = primes.indexOf(j);
        if (index != -1)
          primes.remove(index);
      }
    }
    return primes;
  }

  public static List<Integer> generatePrimesBoolean(int n) {
    boolean[] primes = new boolean[n + 5];
    for (int i = 0; i <= n; i++)
      primes[i] = false;
    primes[2] = primes[3] = true;

    for (int i = 6; i <= n; i+=6) {
      primes[i + 1] = true;
      primes[i - 1] = true;
    }

    for (int i = 0; i <= n; i++) {
      if (primes[i]) {
        int k = i;
        for (int j = k * k; j <= n && j > 0; j += k) {
          primes[j] = false;
        }
      }
    }

    int approximateSize = getApproximateSize(n);
    List<Integer> primesList = new ArrayList<>(approximateSize);
    for (int i = 0; i <= n; i++)
      if (primes[i])
        primesList.add(i);

    return primesList;
  }

  private static int getApproximateSize(int n) {
    // Prime Number Theorem. Round up
    int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
    return approximateSize;
  }

  public static List<Integer> generatePrimesLinkedList(int n) {
    List<Integer> primes = new LinkedList<>();
    primes.add(2);// explicitly add
    primes.add(3);// 2 and 3

    for (int i = 6; i <= n; i+=6) {
      // get all the numbers which can be generated by the formula
      primes.add(i - 1);
      primes.add(i + 1);
    }

    for (int i = 0; i < primes.size(); i++) {
      int k = primes.get(i);
      for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
        int primeCandidate = iterator.next();
        if (primeCandidate == k)
          continue; // Always skip yourself
        if (primeCandidate == (primeCandidate / k) * k)
          iterator.remove();
      }
    }
    return primes;
  }

  public static void main(String... args) {
    int initial = 4000;

    for (int i = 0; i < 12; i++) {
      int n = initial * i;
      long start = System.currentTimeMillis();
      List<Integer> result = generatePrimesArrayList(n);
      long seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tArrayList Seconds: " + seconds);

      start = System.currentTimeMillis();
      result = generatePrimesBoolean(n);
      seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tBoolean Seconds: " + seconds);

      start = System.currentTimeMillis();
      result = generatePrimesLinkedList(n);
      seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tLinkedList Seconds: " + seconds);
    }
  }
}

Et les résultats des derniers essais:

3432    ArrayList Seconds: 430
3432    Boolean Seconds: 0
3432    LinkedList Seconds: 90
3825    ArrayList Seconds: 538
3824    Boolean Seconds: 0
3824    LinkedList Seconds: 81
4203    ArrayList Seconds: 681
4203    Boolean Seconds: 0
4203    LinkedList Seconds: 100
4579    ArrayList Seconds: 840
4579    Boolean Seconds: 0
4579    LinkedList Seconds: 111

Il y a plusieurs choses qui pourraient être optimisés.

pour commencer, les opérations" contains "et" removeAll " sur un ArrayList sont assez coûteuses (linéaire pour le premier, pire cas quadratique pour le second) de sorte que vous pourriez ne pas vouloir utiliser L'ArrayList pour cela. Un hachage-ou TreeSet a de meilleures complexités pour cela, étant presque constante (les complexités de hachage sont bizarres) et logarithmique je pense

, Vous pouvez regarder dans le tamis de tamis D'Eratosthène si vous voulez un tamis plus efficace altogeter, mais ce serait en outre le point de votre question sur le 6K +-1 tour. Il est légèrement mais pas remarquablement plus de mémoire cher que votre solution, mais beaucoup plus rapide.

cette approche peut-elle être beaucoup plus optimisée?

la réponse est oui.

je vais commencer par dire que est une bonne idée d'utiliser le tamis sur un sous-ensemble de nombre dans une certaine gamme, et votre suggestion fait exactement cela.

Lire sur génération de nombres Premiers :

...De plus, basé sur le formalismes de tamis, quelques séquences entières (séquence A240673 in OEIS ) sont construits qui pourraient également être utilisés pour produire des amorces à certains intervalles.

la signification de ce paragraphe est que votre approche de commencer par une liste réduite d'entiers a été effectivement adoptée par l'Académie, mais leurs techniques sont plus efficaces (mais aussi, naturellement, plus complexe).

vous pouvez générer vos numéros d'essai avec une roue, en ajoutant 2 et 4 alternativement, ce qui élimine la multiplication en 6 * k +/- 1.

public void primesTo1000() {
  Set<Integer> notPrimes = new HashSet<>();
  ArrayList<Integer> primes = new ArrayList<>();
  primes.add(2);  //explicitly add
  primes.add(3);  //2 and 3

  int step = 2;
  int num = 5  // 2 and 3 already handled.
  while (num < 1000) {     
    handlePossiblePrime(num, primes, notPrimes);
    num += step;      // Step to next number.
    step = 6 - step;  // Step by 2, 4 alternately.
  }
  System.out.println(primes);
}

probablement la structure de référence standard la plus appropriée pour le tamis D'Eratosthène est le BitSet . Voici ma solution:

static BitSet genPrimes(int n) {
    BitSet primes = new BitSet(n);
    primes.set(2); // add 2 explicitly
    primes.set(3); // add 3 explicitly
    for (int i = 6; i <= n ; i += 6) { // step by 6 instead of multiplication
        primes.set(i - 1);
        primes.set(i + 1);
    }
    int max = (int) Math.sqrt(n); // don't need to filter multiples of primes bigger than max

    // this for loop enumerates all set bits starting from 5 till the max
    // sieving 2 and 3 is meaningless: n*6+1 and n*6-1 are never divisible by 2 or 3
    for (int i = primes.nextSetBit(5); i >= 0 && i <= max; i = primes.nextSetBit(i+1)) {
        // The actual sieve algorithm like in your code
        for(int j = i * i; j <= n; j += i)
            primes.clear(j);
    }
    return primes;
}

Utilisation:

BitSet primes = genPrimes(1000); // generate primes up to 1000
System.out.println(primes.cardinality()); // print number of primes
// print all primes like {2, 3, 5, ...}
System.out.println(primes);
// print all primes one per line
for(int prime = primes.nextSetBit(0); prime >= 0; prime = primes.nextSetBit(prime+1))
    System.out.println(prime);
// print all primes one per line using java 8:
primes.stream().forEach(System.out::println);

la version à base booléenne peut fonctionner plus rapidement pour les petites valeurs n , mais si vous avez besoin, par exemple, d'un million de nombres premiers, BitSet sera plus performant en plusieurs fois et fonctionne réellement correctement. Voici le benchmark boiteux:

public static void main(String... args) {
    long start = System.nanoTime();
    BitSet res = genPrimes(10000000);
    long diff = System.nanoTime() - start;
    System.out.println(res.cardinality() + "\tBitSet Seconds: " + diff / 1e9);

    start = System.nanoTime();
    List<Integer> result = generatePrimesBoolean(10000000); // from durron597 answer
    diff = System.nanoTime() - start;
    System.out.println(result.size() + "\tBoolean Seconds: " + diff / 1e9);
}

sortie:

664579  BitSet Seconds: 0.065987717
664116  Boolean Seconds: 0.167620323

664579 est le nombre correct de nombres premiers inférieurs à 10000000.

cette méthode ci-dessous montre comment trouver les nombres premiers en utilisant la logique 6k+/-1

cela a été écrit en Python 3.6

def isPrime(n):
    if(n<=1):
        return 0
    elif(n<4):   #2 , 3 are prime
        return 1
    elif(n%2==0):  #already excluded no.2 ,so any no. div. by 2 cant be prime
        return 0
    elif(n<9):   #5, 7 are prime and 6,8 are excl. in the above step
        return 1
    elif(n%3==0):
        return 1

    f=5         #Till now we have checked the div. of n with 2,3 which means with 4,6,8 also now that is why f=5
    r=int(n**.5)    #rounding of root n, i.e: floor(sqrt(n))    r*r<=n
    while(f<=r):
        if(n%f==0): #checking if n has any primefactor lessthan sqrt(n), refer LINE 1
            return 0
        if(n%(f+2)==0): #remember her we are not incrementing f, see the 6k+1 rule to understand this while loop steps ,you will see that most values of f are prime
            return 0
        f=f+6

    return 1    

def prime_nos():
    counter=2  #we know 2,3 are prime
    print(2)
    print(3)   #we know 2,3 are prime
    i=1
    s=5  #sum  2+3
    t=0

    n=int(input("Enter the upper limit( should be > 3: "))

    n=(n-1)//6   #finding max. limit(n=6*i+1) upto which I(here n on left hand side) should run
    while(i<n):#2*(10**6)):
        if (isPrime(6*i-1)):   
            counter=counter+1
            print(6*i-1)  #prime no                                                

        if(isPrime(6*i+1)):    
           counter=counter+1
           print(6*i+1)  #prime no                                

        i+=1

prime_nos()  #fn. call