Programme pour trouver tous les nombres premiers dans une très large plage donnée d'entiers

Question

je suis tombé sur cette question suivante sur un site de programmation :Peter souhaite générer des nombres premiers pour son cryptosystème.Aide le!Votre tâche est de générer tous les nombres premiers entre deux nombres donnés !

Saisir

La saisie commence par le nombre t de cas de test sur une seule ligne (t<=10).Dans chacune des t lignes suivantes, il y a deux nombres m et n (1 <= m <= n <= 1000000000, n-m<=100000) séparés par un espace.

J'ai trouvé la solution suivante :

import java.util.*;

public class PRIME1 {
    static int numCases;
    static int left, right;
    static boolean[] initSieve = new boolean[32000];
    static boolean[] answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        numCases = sc.nextInt();
        initSieve[0] = true;
        initSieve[1] = true;
        Sieve();
        for (int j = 0; j < numCases; j++) {
            String line = sc.next();
            String line2 = sc.next();
            left = Integer.parseInt(line);
            right = Integer.parseInt(line2);
            answer = new boolean[right - left + 1];
            getAnswer();
            for (int i = 0; i < answer.length; i++) {
                if (!answer[i]) {
                    int ans = i + left;
                    System.out.println(ans);
                }
            }
            System.out.println();
        }
    }

    public static void Sieve() {

        for (int i = 2; i < 32000; i++) {
            if (!initSieve[i]) {
                for (int j = 2 * i; j < 32000; j += i) {
                    initSieve[j] = true;
                }
            }
            if (i * i > 32000)
                break;
        }
    }

    public static void getAnswer() {
        for (int i = 2; i < 32000 && i <= right; i++) {
            if (!initSieve[i]) {
                int num = i;
                if (num * 2 >= left) {
                    num *= 2;
                } else {
                    num = (num * (left / num));
                    if (num < left)
                        num += i;
                }
                for (int j = num; j >= left && j <= right; j += i) {
                    answer[j - left] = true;
                }
            }
        }
    }
}

J'ai modifié ma solution après avoir lu certaines suggestions.Je reçois toujours une erreur de type délai dépassé.Avez-vous d'autres suggestions sur la façon d'optimiser davantage cela ?Je calcule tous les nombres premiers jusqu'à 32 000, puis je les utilise pour trouver les nombres premiers entre n et m.

Merci, Rohit

Answer 1

On vous donne

1 <= m <= n <= 1000000000, n-m<=100000

ce sont de très petits nombres.Pour filtrer une plage avec une limite supérieure de n, vous avez besoin des nombres premiers pour √n.Ici tu sais n <= 10^9, donc √n < 31623, vous avez donc besoin au pire des nombres premiers à 31621.Il y en a 3401.Vous pouvez les générer avec un tamis standard en quelques microsecondes.

Ensuite, vous pouvez simplement passer au crible la petite plage de m à n en marquant les multiples des nombres premiers que vous avez déjà tamisés, en vous arrêtant lorsque le nombre premier dépasse √n.Une certaine accélération peut être obtenue en éliminant les multiples de certains petits nombres premiers du tamis, mais la logique devient plus compliquée (vous devez traiter les tamis avec des petits nombres premiers). m spécialement).

public int[] chunk(int m, int n) {
    if (n < 2) return null;
    if (m < 2) m = 2;
    if (n < m) throw new IllegalArgumentException("Borked");
    int root = (int)Math.sqrt((double)n);
    boolean[] sieve = new boolean[n-m+1];
    // primes is the global array of primes to 31621 populated earlier
    // primeCount is the number of primes stored in primes, i.e. 3401
    // We ignore even numbers, but keep them in the sieve to avoid index arithmetic.
    // It would be very simple to omit them, though.
    for(int i = 1, p = primes[1]; i < primeCount; ++i) {
        if ((p = primes[i]) > root) break;
        int mult;
        if (p*p < m) {
            mult = (m-1)/p+1;
            if (mult % 2 == 0) ++mult;
            mult = p*mult;
        } else {
            mult = p*p;
        }
        for(; mult <= n; mult += 2*p) {
            sieve[mult-m] = true;
        }
    }
    int count = m == 2 ? 1 : 0;
    for(int i = 1 - m%2; i < n-m; i += 2) {
        if (!sieve[i]) ++count;
    }
    int sievedPrimes[] = new int[count];
    int pi = 0;
    if (m == 2) {
        sievedPrimes[0] = 2;
        pi = 1;
    }
    for(int i = 1 - m%2; i < n-m; i += 2) {
        if (!sieve[i]) {
            sievedPrimes[pi++] = m+i;
        }
    }
    return sievedPrimes;
}

Utilisant un BitSet ou tout autre type de tableau d'indicateurs compressé réduirait l'utilisation de la mémoire et pourrait ainsi accélérer considérablement grâce à une meilleure localisation du cache.

Answer 2

Utilisez un bitset au lieu d'un tableau de Boolean.

public static BitSet primes (final int MAX)
{
     BitSet primes = new BitSet (MAX);
     // make only odd numbers candidates...
     for (int i = 3; i < MAX; i+=2)
     {
        primes.set(i);
     }
     // ... except no. 2
     primes.set (2, true);
     for (int i = 3; i < MAX; i+=2)
     {
        /*
            If a number z is already  eliminated (like 9),
             because it is itself a multiple of a prime 
            (example: 3), then all multiples of z (9) are
            already eliminated.
        */
        if (primes.get (i))
        {
            int j = 3 * i;
            while (j < MAX)
            {
                if (primes.get (j))
                    primes.set (j, false);
                j += (2 * i);
            }
        }
    }
    return primes;
}   

Answer 3

est-ce que tu AVOIR stocker le résultat dans le tableau ?que diriez-vous d'une méthode qui calcule si un entier donné est premier ou non et juste appelle-le pour chaque numéro dans {left,left+1,...,right} ?

Answer 4

Vous pouvez toujours utiliser un décalage lors de l'accès au tableau ISNotprime.

donné m, n:

boolean[] isNotPrime = new boolean[n-m+1];

// to now if number x is primer or not
boolean xIsPrime = isNotPrime[x-m];

ici m est le décalage.

Answer 5

Vous n'êtes pas obligé d'avoir un grand tableau: vous pouvez conserver une liste des nombres premiers trouvés jusqu'à présent et testez à l'aide de plusieurs tableaux, ayant des valeurs= Array_slot + décalage (valeurs déjà testées).Une fois que vous avez terminé les valeurs de I à J, vous ajoutez J-I pour compenser et démarrer un nouveau tableau à partir de j.

Vous pouvez supprimer les nombres pairs de votre tableau, ce qui vous permettrait d'économiser de l'espace (valeurs= array_slot * 2 - 1).

Answer 6

Étant donné que la distance entre M et N est relativement petite, vous pouvez brute la force et utiliser un algorithme de test de primalité rapide dans chaque nombre entre M et N.

Si vous autorisez des algorithmes probabilistes, vous pouvez utiliser Test Miller-Rabin .Soit m= n-m <= 10 ^ 5 et n= n <= 10 ^ 9.La complexité de l'algorithme de force brute serait O (k m (log n) ^ 3), où k est une constante qui contrôle les garanties probabilistes (pour des applications pratiques, K peut être réglée sur 10).

Pour les limites du problème, cette complexité sera d'environ 10 ^ 9.