Algorithme efficace pour obtenir des nombres premiers entre deux grands nombres

Vous faites beaucoup de divisions qui ne sont pas nécessaire - si vous savez qu'un nombre n'est pas divisible par 3, il est inutile de vérifier si elle est divisible par 9, 27, etc. Vous devriez essayer de diviser que par le potentiel de facteurs premiers d'un nombre. Cache de l'ensemble des nombres premiers de la production et ne vérifiez la division par le précédent nombres premiers. Notez que vous avez besoin pour produire la première série de nombres premiers en dessous de L1.

Rappelez-vous que pas de numéro avoir un premier facteur qui est plus grand que sa propre racine carrée, de sorte que vous pouvez arrêter vos divisions à ce point. Par exemple, vous pouvez arrêter la vérification des facteurs potentiels de la numéro 29 après 5.

Vous aussi vous ne pouvez incrémenter par 2 de sorte que vous pouvez ne pas tenir compte de vérifier si un nombre est premier au total (revêtement spécial, le numéro 2, bien sûr.)

J'ai l'habitude de poser cette question au cours des entretiens comme un test, j'ai comparé une mise en œuvre similaire à la vôtre avec l'algorithme que j'ai décrit. Avec l'algorithme optimisé, j'ai pu générer des centaines de milliers de nombres premiers très rapide - je n'ai jamais dérangé d'attente autour de la lenteur, de la mise en œuvre directe.

Nous allons un peu changer ma question: Combien de temps pouvez-vous générer les nombres premiers entre m et n et il suffit d'écrire dans la mémoire? (Ou, éventuellement, à un disque RAM.) D'autre part, souvenez-vous de la gamme de paramètres comme décrit sur la page: m et n peuvent être aussi élevé que un milliard de dollars, tandis que les n-m est à plus d'un million de dollars.

IVlad et Brian plus d'une solution compétitive, même si il est vrai qu'un ralentissement de la solution pourrait être assez bon. Tout d'abord, générer ou même précalculer les nombres premiers inférieurs à sqrt(milliards de dollars); il n'y a pas très nombreuses. Puis faire un tronquée Crible d'Eratosthène: Faire un tableau de longueur n-m+1 pour garder une trace de l'état de chaque nombre dans l'intervalle [m,n], avec initialement une telle marqué comme nombre premier (1). Ensuite, pour chaque précalculées premier p, de faire une boucle qui ressemble à ceci:

for(k=ceil(m/p)*p; k <= n; k += p) status[k-m] = 0;

Cette boucle marques de tous les numéros de la plage de m <= x <= n composite (0) si elle est multiple de p. Si c'est ce que IVlad entend par "assez laid", je ne suis pas d'accord; je ne pense pas que c'est mauvais.

En fait, près de 40% de ce travail est juste pour les nombres premiers 2, 3, et 5. Il existe une astuce pour combiner les tamis pour quelques nombres premiers avec initialisation du tableau de statut. À savoir, le modèle de divisibilité par 2, 3, et 5 répétitions mod 30. Au lieu de l'initialisation de la matrice de tous les 1, vous pouvez initialiser un motif répétitif de 010000010001010001010001000001. Si vous voulez être encore plus tranchant, vous pouvez avancer k par 30*p au lieu de p, et seulement marquer des multiples dans la même tendance.

Après cela, réaliste gains de performance impliquerait des mesures comme l'utilisation d'un vecteur de bits plutôt qu'un char tableau de garder le tamis de données en cache sur processeur. Et initialisation du vecteur de bits par mot plutôt que peu à peu. Cela ne se salissant, et aussi hypothétique puisque vous pouvez arriver au point de générer des nombres premiers plus vite que vous pouvez utiliser. La base du tamis est déjà très rapide et pas très compliqué.

Il existe de nombreux algorithmes de trouver des nombres premiers. Certains sont plus rapides, d'autres sont plus faciles.

Vous pouvez commencer par le plus facile de faire quelques optimisations. Par exemple,

• pourquoi êtes-vous à la recherche si chaque nombre est premier? En d'autres termes, êtes-vous sûr que, compte tenu de toute une gamme de 411 à 418, il est nécessaire de rechercher si le nombre de 412, 414, 416 et 418 premier? Les numéros de diviser par 2 et 3 peuvent être ignorées très simples modifications du code.

• si le nombre n'est pas 5, mais qui se termine par un chiffre '5' (1405, 335), il n'est pas le premier mauvaise idée: il va rendre la recherche plus lent.

• que sur la mise en cache des résultats? Vous pouvez ensuite diviser par des nombres premiers plutôt par chaque nombre. Par ailleurs, seuls les nombres premiers inférieur à la racine carrée du nombre de votre recherche sont concernés.

Si vous avez besoin de quelque chose de vraiment rapide et optimisé, en prenant un algorithme existant plutôt que de réinventer la roue peut être une alternative. Vous pouvez également essayer de trouver des articles scientifiques expliquant comment le faire rapidement, mais il peut être difficile à comprendre et à traduire en code.

import java.io.*;
import java.util.Scanner;
class Test{
public static void main(String args[]){

   Test tt=new Test();
   Scanner obj=new Scanner(System.in);
   int m,n;
      System.out.println(i);
   m=obj.nextInt();
   n=obj.nextInt();
   tt.IsPrime(n,m);
     }
   public void IsPrime(int num,int k)
   {
       boolean[] isPrime = new boolean[num+1];
       //initially assume all integers are prime
        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        //mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= num; i++) {

            //if i is prime, then mark multiples of i as nonprime
            //suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i*j <=num; j++) {
                    isPrime[i*j] = false;
                }
            }
        } 
        for (int i =k; i <= num; i++) {
            if (isPrime[i]) 
            {
                     System.out.println(i);
            }
        }

    }

}

List<int> prime(int x, int y)
    {
        List<int> a = new List<int>();
        int b = 0;
        for (int m = x; m < y; m++)
        {
            for (int i = 2; i <= m / 2; i++)
            {
                b = 0;
                if (m % i == 0)
                {
                    b = 1;
                    break;
                }
            }
            if (b == 0) a.Add(m)`
        }
      return a;
   }