Somme de tous les nombres premiers moins de 2 millions

Question

J'ai fait un programme qui retourne la somme de tous les nombres premiers moins de 2 millions. Je ne sais vraiment pas ce qui se passe avec celui-ci, je reçois 142.891.895.587 comme ma réponse quand la bonne réponse est 142913828922. Il semble que son manque quelques nombres premiers là-dedans. Je suis sûr que la fonction getPrime fonctionne comme il est censé le faire. Je l'ai utilisé une ou deux fois avant et travaillé correctement que. Le code est le suivant:

vector<int> getPrimes(int number);

int main()
{

    unsigned long int sum = 0;
    vector<int> primes = getPrimes(2000000);

    for(int i = 0; i < primes.size(); i++)
    {
        sum += primes[i];
    }

    cout << sum;

    return 0;
}


vector<int> getPrimes(int number)
{

    vector<bool> sieve(number+1,false);
    vector<int> primes;
    sieve[0] = true;
    sieve[1] = true;

    for(int i = 2; i <= number; i++)
    {
        if(sieve[i]==false)
        {
            primes.push_back(i);
            unsigned long int temp = i*i;
            while(temp <= number)
            {
                sieve[temp] = true;
                temp = temp + i;
            }
        }
    }
    return primes;
}

Answer 1

Le i*i d'expression parce que i est déborde un int. Il est tronqué avant d'être affecté à temp. Pour éviter le débordement, le jeter. static_cast<unsigned long>( i ) * i

Mieux encore, mettre fin à l'itération avant cette condition se produit:. for(int i = 2; i*i <= number; i++)

Testé fixe.

Par ailleurs, vous êtes un peu (un) la chance que cela ne produit pas des nombres premiers supplémentaires ainsi que quelques-uns manquants: la valeur de int est signé, et pourrait être négative en cas de débordement, et par ma lecture de §4.7 / 2, cela causerait la boucle interne pour sauter.

Answer 2

Vous pouvez exécuter dans les limites des types de données: http://en.wikipedia.org/wiki/Long_integer .

Answer 3

Cette ligne est le problème:

unsigned long int temp = i*i;

Answer 4

Je vais vous donner un indice. Jetez un oeil de plus près à la valeur initiale que vous donnez à temp. Quelle est la première valeur que vous excluez de sieve? Y at-il d'autres petits multiples de i qui devraient également être exclus? Quelles sont les différentes valeur initiale que vous pourriez utiliser pour vous assurer que tous les bons chiffres se sautées?

Il y a quelques techniques que vous pouvez utiliser pour aider à comprendre cela vous-même. La première est d'essayer d'obtenir votre programme de travail en utilisant une limite inférieure. Au lieu de 2 millions, essayer, par exemple, 30. Il est assez petit pour que vous pouvez calculer la bonne réponse rapidement à la main, et même marcher à travers votre programme sur papier une ligne à la fois. Cela vous permettra de découvrir où les choses commencent à mal tourner.

Une autre option consiste à utiliser un débogueur pour marcher à travers votre ligne par ligne de programme. Débogueurs sont des outils puissants, mais ils ne sont pas toujours faciles à apprendre.

Au lieu d'utiliser un débogueur pour tracer votre programme, vous pouvez imprimer des messages que votre programme a progressé. Dites, faites-le imprimer chaque numéro dans le résultat de getPrimes au lieu d'imprimer seulement la somme. (C'est une autre raison pour laquelle vous voulez essayer une limite inférieure d'abord -. Pour éviter d'être submergé par le volume de la production)

Answer 5

Votre plate-forme doit avoir languit 64 bits. Cette ligne:

unsigned long int temp = i * i;

ne calcule pas correctement parce que j'est déclarée int et le résultat de la multiplication est également int (32 bits). Forcer la multiplication être longue:

unsigned long int temp = (unsigned long int) i * i;

Sur mon système, longue est de 32 bits, donc je devais changer à la fois temp et sum à unsigned long long.