Solo sobre primos (método incremental rápido para calcular primos)

Una vez que pensaste seriamente, ¿qué es mínimamente necesario para calcular una secuencia de primos desde el primero hasta N? Tomamos todo lo que necesitamos y descartamos innecesarios: la receta para una estrategia exitosa. En este caso, es necesario poner en servicio todas las operaciones rápidas y descartar todas las que requieren mucha mano de obra, como la división. Y el que decidió describir los números primos a través de las operaciones de división parece haber jugado una mala pasada a la humanidad. Pasaron milenios y la gente sigue compartiendo ...

Primer código:

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;
}

Ahora una explicación.

, .

API P2P .

, -.

3 :

:

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

, .

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

En el rango de 2 a 3.000.000 se encuentran 216.816 primos.

Ejemplo de Android

PD: A pesar de la lentitud de las operaciones, los rangos de los números primos se calculan por el tamiz de Eratóstenes o simplemente se comprueba la simplicidad de los números individuales. Pero cuando se necesita su secuencia completa, entonces es necesario pensar aproximadamente en la misma línea que se describió anteriormente.
Pero el tamiz todavía itera sobre todos los números, tratando de dividir el número probado en ellos. Su única "ventaja" es que no desperdicia memoria al almacenar cálculos intermedios. Pero, tal vez, lleva más tiempo verificar un número que encontrar todos los números primos anteriores mediante este algoritmo.