Finden Sie die Liste der Primzahlen in kürzester Zeit

Die gute Sache in Ihrem primality test ist, dass Sie nur die Division durch Primzahlen.

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Das schlimme ist, dass Sie dividieren durch alle Primzahlen bisher gefunden, dass alle Primzahlen, die kleiner als die Kandidaten. Das bedeutet, dass die größte Primzahl unterhalb einer million, 999983, Sie teilen sich durch 78497 Primzahlen zu finden heraus, dass diese Zahl eine Primzahl ist. Das ist eine Menge Arbeit. So viel, in der Tat, dass der Aufwand für die Primzahlen in diesem Algorithmus werden die Konten für etwa 99,9% aller Arbeit, wenn man zu einer million, einen größeren Teil für die höheren limits. Und dieser Algorithmus ist fast quadratisch, zu finden, die Primzahlen zu n auf diese Weise, werden Sie brauchen, um über

n² /(2*(log n)²)

Divisionen.

Eine einfache Verbesserung ist das stoppen der division früher. Lassen Sie n eine zusammengesetzte Zahl (also eine Zahl greter als 1 Teiler außer 1 und n), und lassen Sie d ein Teiler von n.

Nun d ein Teiler von n bedeutet, dass n/d ist eine ganze Zahl, und auch ein Teiler von n: n/(n/d) = d.
So können wir natürlich die Gruppe der Teiler von n in Paaren, jeder divisor d gibt Anlass zu der paar (d, n/d).

Für ein solches paar, es gibt zwei Möglichkeiten:

1. d = n/d, was bedeutet, dass n = d² oder d = √n.
2. Die beiden unterschiedlich sind, dann ist einer von Ihnen ist kleiner als die anderen, sagen d < n/d. Aber, die sofort übersetzt d² < n oder d < √n.

So, so oder so, jedes paar Teiler enthält (mindestens) eine nicht mehr als √n damit wenn n ist eine zusammengesetzte Zahl ist, deren kleinster Teiler (außer 1) nicht überschreiten √n.

So können wir stoppen Sie die trial-division, wenn wir erreicht haben √n:

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            //We have not found a divisor less than √n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Hinweis: das kommt auf die Liste der Primzahlen wird iteriert in aufsteigender Reihenfolge. Wenn das nicht gewährleistet ist, durch die Sprache, müssen Sie eine andere Methode verwenden, Durchlaufen von index durch eine ArrayList oder sowas.

Beenden der trial division der Quadratwurzel der Kandidaten, für die größte Primzahl unterhalb einer million, 999983 wir jetzt nur noch brauchen, teilen Sie diese durch die 168 Primzahlen kleiner als 1000. Das ist viel weniger Arbeit als zuvor. Stoppen Sie die trial-division der Quadratwurzel und Division nur durch Primzahlen, ist so gut als trial-division kann und muss

2*n^1.5 /(3*(log n)²)

Divisionen, für n = 1000000, das ist ein Faktor von etwa 750, nicht schlecht, oder?

Aber das ist noch nicht sehr effizient, die effizientesten Methoden zu finden, die alle Primzahlen unter n werden durchsiebt. Einfach zu implementieren, ist die klassische Sieb des Eratosthenes. Findet sich in den Primzahlen unter n in O(n*log log n) Operationen, mit einigen Verbesserungen (Beseitigung von vielfachen von verschiedenen kleinen Primzahlen von der Berücksichtigung im Voraus), Ihre Komplexität kann reduziert werden auf O(n) Operationen. Ein relativ neues Sieb mit einer besseren asymptotischen Verhalten der Sieb des Atkin, mit dem man die Primzahlen zu n in O(n) Operationen, oder mit der Erweiterung der Beseitigung der vielfachen einige kleine Primzahlen in O(n/log log n) Operationen.
Das Sieb von Atkin ist komplizierter zu implementieren, so ist es wahrscheinlich, dass eine gute Umsetzung des Sieb des Eratosthenes führt besser als eine naive Implementierung des Sieb des Atkin. Für Implementierungen, wie die Optimierung Ebenen, der performance-Unterschied ist gering, es sei denn, die Grenze wird zu groß (größer als 10¹⁰; und es ist nicht ungewöhnlich, dass in der Praxis ein Sieb von Eratosthenes besser skaliert als ein Sieb von Atkin darüber hinaus, aufgrund der besseren memory-access-patterns). Also würde ich empfehlen, beginnend mit einem Sieb von Eratosthenes, und nur dann, wenn seine Leistung nicht zufriedenstellend trotz ehrlicher Bemühungen um Optimierung, Tauchen Sie ein in das Sieb von Atkin. Oder, wenn Sie nicht wollen, es selbst implementieren, finden Sie eine gute Umsetzung, jemand anderes hat bereits ernsthaft dran.

Ich habe in ein bisschen mehr detail in eine Antwort mit einer etwas anderen Einstellung, wo das problem war das finden der n-TEN Primzahl. Einige Implementierungen von mehr oder weniger effizienten Methoden verlinkt sind, die Antworten, insbesondere ein oder zwei brauchbare (wenn auch nicht viel optimiert) Implementierungen des Sieb des Eratosthenes.

Verstehe ich eine Primzahl ist eine Zahl, die ist nur teilbar durch sich selbst und die Zahl 1 (ohne Rest). Sehen Wikipedia-Artikel

Dass gesagt wird, verstehe ich nicht, der Algorithmus sehr gut in den zweiten Kommentar, aber eine kleine Verbesserung Ihrer Algorithmus wäre zu ändern, Ihre for-Schleife:

for (int i = 5; i < 100000; i = i + 2) {
    if (checkMod(i)) {
        primes.add(i);
    }
}

Diese basiert auf der Annahme, dass 1, 2, und 3 sind alle Primzahlen und alle geraden zahlen danach sind keine Primzahlen. Zumindest schneidet Ihr Algorithmus in der Hälfte.

Schön erklärt von @Daniel Fischer.

Einer Implementierung in C++ aus seiner Erklärung:

#include<iostream>

using namespace std;

long* getListOfPrimeNumbers (long total)
{
  long * primes;
  primes = new long[total];
  int count = 1;
  primes[0] = 2;
  primes[1] = 3;
  while (count < total)
  {
    long composite_number = primes[count] + 2;
    bool is_prime = false;
    while (is_prime == false)
    {
      is_prime = true;
      for (int i = 0; i <= count; i++)
      {
        long prime = primes[i];
        if (prime * prime > composite_number)
        {
          break;
        }
        if (composite_number % prime == 0)
        {
          is_prime = false;
          break;
      }
      }
      if (is_prime == true)
      {
        count++;
        primes[count] = composite_number;
      }
      else
      {
        composite_number += 2;
    }
  }
  }
  return primes;
}

int main()
{
  long * primes;
  int total = 10;
  primes = getListOfPrimeNumbers(total);
  for (int i = 0; i < total; i++){
    cout << primes[i] << "\n";
  }
  return 0;
}