Programma per trovare tutti i primi in una gamma di numeri interi molto amanti

Question

Ho trovato questa seguente domanda su un sito web di programmazione: Peter vuole generare alcuni numeri primi per il suo crittosistema.Aiutalo!Il tuo compito è generare tutti i numeri primi tra due numeri dati!

Ingresso

L'ingresso inizia con il numero T dei casi di test in una singola riga (T <= 10).In ciascuna delle seguenti linee T ci sono due numeri M e N (1 <= m <= n <= 1000000000, n-m <= 100000) separati da uno spazio.

Ho inventato la seguente soluzione:

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

.

Ho modificato la mia soluzione dopo aver letto alcuni suggerimenti.Sto ancora ottenendo un limite di tempo superato il tipo di errore.Altri suggerimenti come come ulteriormente ottimizzare questo?Sto calcolando tutte le prime fino a 32000 e quindi usando questi per trovare i numeri primi tra n a m.

Grazie, Rohit

Answer 1

ti viene dato

.

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

Questi sono numeri molto piccoli. Per setacciare una gamma con un limite superiore di n, è necessario i numeri PREMES a √n. Qui conosci n <= 10^9, quindi √n < 31623, quindi è necessario il peggiore dei PREMES a 31621. Ci sono 3401. Puoi generarli con un setaccio standard in alcuni microsecondi.

Quindi puoi semplicemente setacciare la piccola gamma da m a n marcando i multipli dei primi che hai setacciato prima, arrestati quando il Prime supera √n. Alcuni accelerazioni possono essere acquisiti eliminando i multipli di alcuni piccoli numeri primi dal setaccio, ma la logica diventa più complicata (è necessario trattare setacci con piccolo m specialmente).

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

.

L'utilizzo di un BitSet o qualsiasi altro tipo di array flag confezionato ridurrebbe l'utilizzo della memoria e quindi può fornire un significativo velocità a causa di una migliore cache-località.

Answer 2

Utilizzare un bitset invece di una serie di booleani.

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

Fai Avere per memorizzare il risultato nell'array?Che ne dici di un metodo che calcola se un determinato intero è un primo o no e solo chiamalo per ogni numero in {left,left+1,...,right}?

Answer 4

È sempre possibile utilizzare un offset quando si accede all'array ISNotPrime.

Dato M, N:

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

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

.

qui è l'offset.

Answer 5

Non sei costretto ad avere un grande array: è possibile mantenere un elenco dei primi trovati finora, e verificare utilizzando più array, aventi valori= array_slot + offset (valori già testati).Dopo aver terminato i valori da I to J, aggiungi J-I per compensare e avviare un nuovo array a partire da J.

È possibile rimuovere anche numeri dal tuo array, che ti salverà un po 'di spazio (valori= array_slot * 2 - 1).

Answer 6

Poiché la distanza tra M e N è relativamente piccola, è possibile bruta forza e utilizzare un rapido algoritmo di prova di primalità in ogni numero tra M e N.

Se si consentono algoritmi probabilistici, è possibile utilizzare Test Miller-Rabin .Sia m= n-m <= 10 ^ 5 e n= n <= 10 ^ 9.La complessità dell'algoritmo di forza bruta sarebbe o (k m (log n) ^ 3), dove K è una costante che controlla garanzie probabilistiche (per applicazioni pratiche, K può essere impostata su 10).

Per i limiti del problema, questa complessità sarà di circa 10 ^ 9.