Was ist eine effiziente Methode, um Tausende von Zahlen schnell hinzuzufügen?

Question

Ich versuche, eine Herausforderung zu lösen, aber ich habe eine Straßensperre getroffen. Ich bin ein Anfänger Programmierer, der versucht, Zehntausende von Zahlen hinzuzufügen. Wenn ich lange genug warte, kann mein Programm leicht die richtige Summe liefern, aber ich suche nach einer effizienteren Methode.

Was ist eine effiziente Methode, um schnell Tausende von Zahlen hinzufügen?

Randbemerkung: Ich habe über modulare Arithmetik zu lesen, aber ich kann nicht ganz meinen Kopf wickeln um ihn herum. Nicht sicher, ob das für diese Situation nützlich sein könnte.

ich die Summe von jeder Primzahl unter 2 000 000. Hier zu erhalten bin versucht, ist mein Code so weit:

public class Problem10 { 
    public static void main (String[] args) { 
     long sum = 0L; 

     for(long i = 1L; i < 2000000; i++) { 
      if(isPrimeNumber((int)i)) { 
       sum += i; 
      } 
     } 
     System.out.println(sum); 
    } 

    public static boolean isPrimeNumber(int i) { 
     int factors = 0; 
     int j = 1; 

     while (j <= i) { 
      if (i % j == 0) { 
       factors++; 
      } 
      j++; 
     } 
     return (factors == 2); 
    } 
} 

Answer 1

Sie können Ihre isPrimeNumber() Methode mit diesem ersetzen es wesentlich zu beschleunigen.

public static boolean isPrimeNumber(int i) { 
    if (i==2) return true; 
    if (i==3) return true; 
    if (i%2==0) return false; 
    if (i%3==0) return false; 

    int j = 5; 
    int k = 2; 

    while (j * j <= i) { 
     if (i % j == 0) return false; 
     j += k ; 
     k = 6 - k; 

    } 
    return true; 
} 

Answer 2

Diese wie Hausaufgaben aussieht, also werde ich nicht, dass Sie die Lösung geben in Code. Das Mindeste, was Sie tun können, ist, es selbst zu programmieren.

---

in Ihrem Code isPrimeNumber() ist das, was die meisten der oben ist die Zeit nehmen-wenn ich raten müsste, würde ich 90-99% davon sagen. Was Sie tun können, um es schneller zu machen, implementieren Sie die Sieve of Eratosthenes.

Um zu beginnen, erstellen Sie ein Array, das alle Primzahlen enthält. Sie sollten es mit einem einzelnen Wert beginnen: 2. Um mehr Primzahlen zu finden, durchlaufen Sie jede ganze Zahl von 3 bis zur höchsten Zahl, die Sie wollen. Überprüfen Sie für jede dieser Zahlen, ob diese Zahl durch eine der Primzahlen in Ihrem Array teilbar ist. Wenn die nächste Primzahl in Ihrem Array größer als i/2 ist, wissen Sie, dass i prim ist, und Sie können es zu Ihrem Array hinzufügen.

Nachdem Sie alle Primzahlen von 1 bis n gefunden, der einzige Weg, sie zu fassen ist, indem sie durch das Array iterieren. Dieser Teil kann nicht optimiert werden, aber es wird sowieso nicht lange dauern.

Es gibt zwei Möglichkeiten, dies zu tun. Eine besteht darin, einfach eine ArrayList oder LinkedList zu verwenden und Zahlen nach Bedarf hinzuzufügen. Die andere Möglichkeit besteht darin, ein Array zu erstellen, das so groß oder größer ist, wie Sie benötigen. Wie here erwähnt, ist die Anzahl der Primzahlen gleich oder kleiner als n kleiner als (n/log(n)) * (1 + 1.2762/log(n)), solange n größer als 598. ist, wenn n kleiner als 598 ist, können Sie einfach eine Reihe von Länge erstellen 109.

---

in Bezug auf die Frage im Titel: „Was schnell für das Hinzufügen von Tausenden von Zahlen eine effiziente Methode ist?“, das einzige, was ich ist Multithreading denken kann. Erstellen Sie ein Array mit allen Zahlen, die Sie addieren möchten, und viele Threads summieren die verschiedenen Teile des Arrays. Danach summiere alle Ergebnisse von jedem Thread. Diese Methode wird wahrscheinlich nur merklich schneller sein, wenn eine große Anzahl von Zahlen, z. Hunderttausende oder Millionen.