Question

Je tente de créer cette fonction d'assistance en C # qui retourne les nombres premiers n premiers. J'ai décidé de stocker les numéros dans un dictionnaire au format <int,bool>. La clé est le numéro en question et le bool représente si l'int est un premier ou non. Il y a une tonne de ressources là-bas le calcul / la génération des nombres premiers (SO inclus), donc je pensais à se joindre aux masses en élaborant un générateur de nombres premiers trivial.

Ma logique est la suivante: 

public static Dictionary<int,bool> GetAllPrimes(int number)
    {
        Dictionary<int, bool> numberArray = new Dictionary<int, bool>();


        int current = 2;
        while (current <= number)
        {
            //If current has not been marked as prime in previous iterations,mark it as prime
            if (!numberArray.ContainsKey(current))
                numberArray.Add(current, true);

            int i = 2;
            while (current * i <= number)
            {
                if (!numberArray.ContainsKey(current * i))
                    numberArray.Add(current * i, false);
                else if (numberArray[current * i])//current*i cannot be a prime
                    numberArray[current * i] = false;
                i++;

            }
            current++;
        }
        return numberArray;
    }

Il sera grand si le sage me fournir des suggestions, des optimisations, avec refactorisations possibles. Je me demandais aussi si l'inclusion du dictionnaire aide à l'exécution de cet extrait.

Était-ce utile?

La solution

Le stockage des entiers doit explicitement au moins 32 bits par nombre premier, avec une surcharge de la structure du conteneur.

Vers 2 31 , la valeur maximale d'un entier signé 32 bits peut prendre, au sujet de chaque numéro de 21.5th est premier. Les petits nombres premiers sont des nombres plus dense, d'environ 1 à ln (n) est d'environ premier n.

Cela signifie qu'il est plus efficace de la mémoire d'utiliser un tableau de bits que les numéros de magasin explicitement. Il sera également beaucoup plus rapide pour rechercher si un nombre est premier, et assez rapide pour itérer les nombres premiers.

Il semble que ceci est appelé BitArray en C # (en Java, il est BitSet).

Autres conseils

La première chose qui tracasse est que, pourquoi vous stockez le numéro lui-même?

Tu ne peux pas utiliser l'index lui-même qui représentera le nombre?

PS: Je ne suis pas un développeur c # alors peut-être il est impossible avec un dictionnaire, mais il peut être fait avec la structure appropriée.

Tout d'abord, il suffit de boucler jusqu'à ce la racine carrée du nombre. Faire tous les faux numéros par défaut et un drapeau simple que vous définissez vrai au début de chaque itération.

En outre, ne stocke pas dans un dictionnaire. Faire un tableau de bool et ont l'indice soit le numéro que vous recherchez. Seulement 0 aura aucun sens, mais cela n'a pas d'importance. Vous n'avez pas à init soit; bools sont fausses par défaut. Il suffit de déclarer une bool[] de longueur de number.

Alors, je l'init comme ceci: 

primes[2] = true;
for(int i = 3; i < sqrtNumber; i += 2) {

}

Alors vous sautez tous les chiffres même automatiquement.

Par ailleurs, ne jamais déclarer une variable (i) dans une boucle, il le rend plus lent.

qui est à ce sujet. Pour plus d'informations voir cette page.

Je suis assez sûr que le fait Dictionary fait mal performances, car il ne vous permet pas d'effectuer les divisions d'essai dans un ordre optimal. Traditionnellement, vous stocker les nombres premiers connus afin qu'ils puissent être itérée du plus petit au plus grand, puisque les petits nombres premiers sont des facteurs de nombres plus composites que les nombres premiers plus grands. En outre, vous ne devez jamais essayer de division avec une prime plus grande que la racine carrée du premier candidat.

Beaucoup d'autres optimisations sont possibles (comme vous le soulignez, ce problème a été étudié à la mort), mais ce sont ceux que je peux voir sur le dessus de ma tête.

Le dictionnaire n'a vraiment pas de sens ici - simplement stocker tous les nombres premiers jusqu'à un nombre donné dans une liste. Procédez ensuite comme suit: 

Is given number in the list?  
    Yes - it's prime.  Done.
Not in list
Is given number larger than the list maximum?
    No - it's not prime.  Done.
Bigger than maximum; need to fill list up to maximum.
Run a sieve up to given number.
Repeat.

1) Du point de vue du client à cette fonction, ne serait-il mieux si le type de retour est bool [] (de 0 à number peut-être)? En interne, vous avez trois états (KnownPrime, KnownComposite, Unknown), qui pourrait être représenté par une énumération. Le stockage d'un tableau de cette énumération interne, prérempli Unknown, sera plus rapide qu'un dictionnaire.

2) Si vous restez avec le dictionnaire, la partie du tamis que les marques multiples du nombre actuel en composite pourrait être remplacé par un modèle de numberArray.TryGetValue() plutôt que plusieurs contrôles pour ContainsKey et récupération ultérieure de la valeur par clé.

Le problème avec le retour d'un objet qui contient les nombres premiers est que si vous êtes prudent de le rendre immuable, le code client est libre de gâcher les valeurs, à son tour, ce qui signifie que vous n'êtes pas en mesure de mettre en cache les nombres premiers que vous avez déjà calculé.

Que diriez-vous d'avoir une méthode telle que: 

bool IsPrime(int primeTest);

dans votre classe d'aide qui peut masquer les nombres premiers, il est déjà calculé, ce qui signifie que vous n'avez pas à recalculer les chaque fois.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top