Fast über Primzahlen (schnelle inkrementelle Methode zur Berechnung von Primzahlen)

Haben Sie einmal ernsthaft darüber nachgedacht, was minimal notwendig ist, um eine Folge von Primzahlen von der ersten bis zur N zu berechnen? Wir nehmen alles, was wir brauchen, und werfen es unnötig weg - das Rezept für eine erfolgreiche Strategie. In diesem Fall ist es notwendig, alle schnellen Vorgänge in Betrieb zu nehmen und alle arbeitsintensiven Vorgänge wie die Teilung zu verwerfen. Und derjenige, der beschlossen hat, Primzahlen durch Divisionsoperationen zu beschreiben, scheint der Menschheit einen Streich gespielt zu haben. Jahrtausende sind vergangen und die Menschen teilen immer noch ...

Erster Code:

public HashMap<Long, Long> serialPrimes() {
   long range = Long.parseLong(this.range.getText().toString());
   HashMap<Long, Long> primes = new HashMap<>(); //    
   HashMap<Long, ArrayList<Long>> spectres = new HashMap<>(); //     
   HashMap<Long, ArrayList<Long>> toppings = new HashMap<>(); //      
   for(long i = 2; i < range; i++){
       if(toppings.keySet().contains(i)) { //      ,     i
           //  
           ArrayList<Long> spectre = toppings.get(i);
           spectres.put(i, spectre);
           toppings.remove(i);
           for(long spectreValue : spectre) {
               //      
               long topping = primes.get(spectreValue) + spectreValue;
               primes.put(spectreValue, topping);
               //    
               if(toppings.keySet().contains(topping)) {
                   toppings.get(topping).add(spectreValue);
               } else {
                   ArrayList<Long> newSpectre = new ArrayList<>();
                   newSpectre.add(spectreValue);
                   toppings.put(topping, newSpectre);
               }
           }
       } else { //      ,     i
           //   
           primes.put(i, i + i); //       ,   
   //   
           //     
           ArrayList<Long> newSpectre = new ArrayList<>();
           newSpectre.add(i);
           toppings.put(i + i, newSpectre);
       }
   }
   return primes;
}

Nun eine Erklärung.

, .

API P2P .

, -.

3 :

:

• , 2 ()
• T
• ,
• 2*n (, 2[4])
• 4[2]
• ,
• ( , )

, .

1.500.000. , 2 . -, 3.000.000. 96 , 14 ( , ).

Im Bereich von 2 bis 3.000.000 liegen 216.816 Primzahlen.

Android Beispiel

PS: Trotz der Langsamkeit der Operationen werden die Primzahlenbereiche durch das Eratosthenes-Sieb berechnet oder überprüfen Sie einfach einzelne Zahlen auf Einfachheit. Wenn jedoch ihre vollständige Abfolge benötigt wird, ist es notwendig, ungefähr in der gleichen Weise wie oben beschrieben zu denken.
Das Sieb durchläuft jedoch immer noch alle Zahlen und versucht, die getestete Zahl in diese zu unterteilen. Der einzige „Vorteil“ besteht darin, dass beim Speichern von Zwischenberechnungen kein Speicher verschwendet wird. Aber vielleicht dauert es länger, eine Zahl zu überprüfen, als alle vorherigen Primzahlen mit diesem Algorithmus zu finden.