À propos des nombres premiers (méthode incrémentielle rapide pour calculer les nombres premiers)

Une fois que vous avez sérieusement pensé à ce qui est minimalement nécessaire pour calculer une séquence de nombres premiers du premier à N? Nous prenons tout ce dont nous avons besoin et éliminons les inutiles - la recette d'une stratégie réussie. Dans ce cas, il est nécessaire de mettre en service toutes les opérations rapides et de rejeter toutes celles à forte intensité de main-d'œuvre, comme la division. Et celui qui a décidé de décrire les nombres premiers par le biais d'opérations de division semble avoir joué un tour à l'humanité. Des millénaires sont passés et les gens continuent de partager ...

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

Maintenant une explication.

, .

API P2P .

, -.

3 :

:

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

, .

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

Dans la plage de 2 à 3.000.000 se trouve 216.816 nombres premiers.

Exemple Android

PS: Malgré la lenteur des opérations, les plages de nombres premiers sont calculées par le tamis d'Ératosthène ou vérifient simplement la simplicité des nombres individuels. Mais lorsque leur séquence complète est nécessaire, il est nécessaire de penser approximativement dans la même veine que celle décrite ci-dessus.
Mais le tamis itère toujours sur tous les nombres, essayant de diviser le nombre testé en eux. Son seul «avantage» est de ne pas perdre de mémoire lors du stockage de calculs intermédiaires. Mais, peut-être, cela prend plus de temps pour vérifier un nombre que de trouver tous les nombres premiers précédents par cet algorithme.