encontrar todos los números primos en un rango dado

Question

Estoy escribiendo este programa en Java que se encuentra todos los números primos entre un rango determinado.Porque yo estoy tratando realmente grandes números de mi código parece no ser lo suficientemente rápido y me da un error de tiempo.Aquí está mi código, ¿alguien sabe para que sea más rápido?Gracias.

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

obtendrás una mejora enorme simplemente cambiando esto:

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

a esto:

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

El código actual se regenera los tiempos del código de generación general de tamiz, pero en realidad solo necesita generarlo una vez.

Answer 2

El problema obvio es que está informando los primos de hasta 1000000 muchas veces (Zrange - XRange Times).Otra es que no necesita calcular los primos de hasta 1000000, solo necesita verificar los primos hasta Zrange, por lo que está perdiendo el tiempo cuando Zrange <1000000 y obtenga un desbordamiento de búfer cuando ZRANGE> 1000000.

Answer 3

Puede iniciar el bucle interno de i*i, es decir,en lugar de for (int j = i * 3; j <= n; j += i << 1) usted puede escribir for (int j = i * i; j <= n; j += i << 1) para un / a menor velocidad.

También, usted tiene que estar seguro de que su zrange no es mayor que 1000000.

Si xrange es mucho mayor que sqrt(zrange), usted puede también dividir el tamiz de la matriz en dos, por un desplazamiento de tamiz esquema.La parte inferior de la matriz tendrá una duración de 2 a sqrt(zrange).El superior tendrá una duración de xrange a zrange.Como usted tamiz de la parte inferior de la matriz, ya que cada nuevo primer convierte identificados por ello, dentro de su bucle interno, además de marcar la parte inferior de la matriz hasta su final también tamiz de la parte superior de la matriz.Usted tendrá que calcuate el desplazamiento inicial de cada uno de los prime i, y uso el mismo paso de 2*i para la mitad inferior.Si su rango es más amplio que un par de números primos, obtendrá la ventaja de velocidad (de lo contrario sólo la división de juicios por odds será suficiente).

Otra cosa a probar es, si iguala > 2 no son primos de todos modos, ¿por qué representan en la matriz y de los residuos de la mitad del espacio?Usted puede tratar cada uno de los i como la representación de un número impar, 2*i+1, así la compresión de su matriz en la mitad.

El último truco sencillo es eliminar los múltiplos de 3 de antemano así, mediante la marcación de ON no sólo odds (es decir,coprimes con 2), por { ... i+=2; ...}, pero sólo coprimes con 2 y 3, por { ... i+=2; ... i+=4; ... } en su lugar.También, al marcar OFF los múltiplos de los números primos > 3, uso { ... j+=2*i; ... j+=4i; ...} demasiado.E. g., en 5*5, 5*7, 5*9, 5*11, ... usted no necesita marcar OFF 5*9, si no varios de 3 fue marcado ON en el primer lugar.