Apenas sobre números primos (método incremental rápido para calcular números primos)

Uma vez que você pensou seriamente o que é minimamente necessário para calcular uma sequência de primos do primeiro ao N? Tomamos tudo o que precisamos e descartamos desnecessariamente - a receita para uma estratégia bem-sucedida. Nesse caso, é necessário levar em serviço todas as operações rápidas e descartar todas as que exigem muita mão-de-obra, como a divisão. E quem decidiu descrever números primos por meio de operações de divisão parece ter pregado uma peça na humanidade. Milênios passaram, e as pessoas ainda continuam a compartilhar ...

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

Agora uma explicação.

, .

API P2P .

, -.

3 :

:

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

, .

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

No intervalo de 2 a 3.000.000, estão 216.816 primos.

Exemplo Android

PS: Apesar da lentidão das operações, os intervalos de números primos são calculados pela peneira de Eratóstenes ou apenas verifica a simplicidade dos números individuais. Mas quando a sequência completa é necessária, você precisa pensar aproximadamente na mesma linha descrita acima.
Mas a peneira ainda repete todos os números, tentando dividir o número testado neles. Sua única "vantagem" é que ela não desperdiça memória ao armazenar cálculos intermediários. Mas, talvez, leve mais tempo para verificar um número do que encontrar todos os números primos anteriores por esse algoritmo.