Trovare tutti i numeri primi in un dato intervallo

Question

Sto scrivendo questo programma Java che trova tutti i numeri primi tra un determinato intervallo.Perché ho a che fare con numeri davvero grandi, il mio codice sembra non essere abbastanza veloce e mi dà un errore temporale.Ecco il mio codice, qualcuno sa che rendere più veloce?Grazie.

import java.util.*;
public class primes2 
{   
    private static Scanner streamReader = new Scanner(System.in);
    public static void main(String[] args)
    {
        int xrange = streamReader.nextInt(); 
        int zrange = streamReader.nextInt();
        for (int checks = xrange; checks <= zrange; checks++)
        {
            boolean[] checkForPrime = Primes(1000000);
            if (checkForPrime[checks])
            {
                System.out.println(checks);
            }
        }
    }
    public static boolean[] Primes(int n)
    {
        boolean[] isPrime = new boolean[n + 1];
        if (n >= 2)
            isPrime[2] = true;
        for (int i = 3; i <= n; i += 2)
            isPrime[i] = true;
        for (int i = 3, end = sqrt(n); i <= end; i += 2)
        {
            if (isPrime[i]) 
            {
                for (int j = i * 3; j <= n; j += i << 1)
                    isPrime[j] = false;
            }
        }
        return isPrime;
    }
    public static int sqrt(int x)
    {
        int y = 0;
        for (int i = 15; i >= 0; i--) 
        {
            y |= 1 << i;
            if (y > 46340 || y * y > x)
                y ^= 1 << i;
        }
        return y;
        }
}

.

Answer 1

Otterrai un miglioramento enorme cambiando questo:

    for (int checks = xrange; checks <= zrange; checks++)
    {
        boolean[] checkForPrime = Primes(1000000);

.

A questo:

    boolean[] checkForPrime = Primes(1000000);
    for (int checks = xrange; checks <= zrange; checks++)
    {

.

Il tuo codice corrente rigenera il setaccio zrange - xrange + 1 Times, ma è effettivamente bisogno solo di generarlo una volta.

Answer 2

Il problema ovvio è che stai calcolando le prime fino a 1000000 molti tempo (zrange - xrange volte).Un altro è che non hai bisogno di calcolare le prime fino a 1000000, hai solo bisogno di controllare le prime fino a Zrange, quindi stai perdendo tempo quando Zrange <1000000 e ottenere un buffer overflow quando zrange> 1000000.

Answer 3

È possibile avviare il ciclo interno da i*i, I.e. Invece di for (int j = i * 3; j <= n; j += i << 1) è possibile scrivere for (int j = i * i; j <= n; j += i << 1) per un minor velocità-up.

Inoltre, devi essere sicuro che il tuo zrange non sia maggiore di 1000000.

Se xrange è molto maggiore di sqrt(zrange), è anche possibile dividere l'array di setaccio in due, per uno schema offset setaccio . L'array inferiore coperà da 2 a sqrt(zrange). La parte superiore si estenderà da xrange a zrange. Mentre setagiri il tuo array inferiore, poiché ogni nuovo primo è identificato da esso, all'interno del tuo loop interiore, oltre a segnare l'array inferiore fino alla fine del setacciare anche l'array superiore. Dovrai calcolare l'offset iniziale per ogni i principale e utilizzare lo stesso passo di 2*i come fai per la metà inferiore. Se la tua gamma è più ampia di pochi primi, riceverai il vantaggio della velocità (altrimenti la divisione di prova da parte delle probabilità sarà sufficiente).

Un'altra cosa da provare è, se Evens > 2 non è comunque prima, perché le rappresentano nell'array e sprecare metà dello spazio? È possibile trattare ogni i come rappresentare un numero dispari, 2*i+1, quindi comprimere la tua matrice a metà.

Ultimo trucco semplice è quello di eliminare anche i multipli di 3 in anticipo , contrassegnando anche ON non solo odds (cioè Coprodimes con 2), con { ... i+=2; ...}, ma solo Coprimes con 2 e 3, da { ... i+=2; ... i+=4; ... } invece. Inoltre, quando si contrassegnando i multipli OFF di PREMS > 3, utilizzare anche { ... j+=2*i; ... j+=4i; ...}. Ad esempio, in 5*5, 5*7, 5*9, 5*11, ... non è necessario contrassegnare OFF 5*9, se nessun multiplo di 3 è stato contrassegnato da ON in primo luogo.