Trouver tous les nombres premiers dans une plage donnée

Question

J'écris ce programme Java qui trouve tous les nombres premiers entre une plage donnée. Parce que je fais face à de très gros chiffres, mon code ne semble pas être assez rapide et me donne une erreur de temps. Voici mon code, est-ce que quelqu'un sait le rendre plus rapide? Merci.

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

Vous obtiendrez un énorme Amélioration simplement en changeant ceci:

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

pour ça:

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

Votre code actuel régénère le tamis zrange - xrange + 1 fois, mais vous n'avez besoin de le générer qu'une seule fois.

Answer 2

Le problème évident est que vous calculez les nombres premiers jusqu'à 1000000 plusieurs fois (Zrange - Times XRange). Un autre est que vous n'avez pas besoin de calculer les nombres premiers jusqu'à 1000000, il vous suffit de vérifier les plates d'origine sur Zrange, donc vous perdez du temps lorsque ZRange <1000000, et obtenez un débordement de tampon lorsque ZRange> 1000000.

Answer 3

Vous pouvez commencer votre boucle intérieure à partir de i*i, c'est-à-dire au lieu de for (int j = i * 3; j <= n; j += i << 1) tu peux écrire for (int j = i * i; j <= n; j += i << 1) Pour une accélération mineure.

De plus, vous devez être sûr que votre zrange n'est pas plus grand que 1000000.

Si xrange est beaucoup plus grand que sqrt(zrange), vous pouvez également diviser votre tableau de tamis en deux, pour un tamis décalé schème. Le tableau inférieur s'étendra de 2 à sqrt(zrange). Le supérieur s'étendra à partir de xrange à zrange. Lorsque vous tamisez votre tableau inférieur, à mesure que chaque nouveau premier est identifié par celui-ci, à l'intérieur de votre boucle intérieure, en plus de marquer le tableau inférieur jusqu'à son extrémité, tamisez également le tableau supérieur. Vous devrez calcuonner le décalage de départ pour chaque premier i, et utilisez la même étape de 2*i Comme vous le faites pour la moitié inférieure. Si votre gamme est plus large que quelques nombres premiers, vous obtiendrez un avantage de vitesse (sinon juste la division d'essai par les cotes suffira).

Une autre chose à essayer est, si Evens > 2 Les nombres premiers ne sont-ils pas de toute façon, pourquoi les représenter dans le tableau et gaspiller la moitié de l'espace? Vous pouvez traiter chacun i comme représentant un nombre impair, 2*i+1, Donc compression Votre tableau en deux.

La dernière astuce simple consiste à éliminer les multiples de 3 à l'avance aussi, en marquant ON pas seulement odds (IE Coprimes avec 2), par { ... i+=2; ...}, mais seulement des coprimes avec 2 et 3, par { ... i+=2; ... i+=4; ... } Au lieu. Aussi, lors du marquage OFF Multiples de nombres premiers > 3, utilisation { ... j+=2*i; ... j+=4i; ...} aussi. Par exemple, dans 5*5, 5*7, 5*9, 5*11, ... Tu n'as pas besoin de marquer OFF 5*9, si aucun multiple de 3 a été marquée ON en premier lieu.