Суммирование простых чисел ниже двух миллионов - PullRequest
Новая
       0

Суммирование простых чисел ниже двух миллионов

0 голосов
/ 26 февраля 2011

Возможно, вы слышали о веб-сайте Project Euler (projecteuler.net).Я работаю над первыми проблемами, которые были довольно тривиальными, и я нахожусь над проблемой, описанной в названии.

Это не об оптимизации или о чем-либо - это занимает около 90 тысячных секундыполный.Это дает мне неправильный итог.

Может ли кто-нибудь мне помочь?Я понятия не имею, почему ответ, который я получаю - как от общего количества массива (итого), так и от общего количества, которое было сложено нормально (всего) - неверно.Ответ, который они оба показывают, - 947402457, и веб-сайт, на котором он говорит мне, является неправильным.

В случае, если это всего лишь формулировка, вопрос здесь: http://projecteuler.net/index.php?section=problems&id=10

Что также оченьСтранно, насколько я могу судить, когда в конце, когда вы можете ввести, какое простое число вы хотите просмотреть (оно вынимает его из массива), оно дает вам правильный ответ. 

#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <ctime>

typedef unsigned long int bignum;
//there are 666671 primes below two million
int main(){
    using namespace std;
    bignum top = 2000000;
    bignum total = 0;
    bignum atotal = 0;
    //hardcode 2 and 3
    total += 5;
    int inc = 2;
    bignum n = 5;
    double sq = n;
    bignum np = 1;
    bignum *pa = new bignum[top];
    pa[0] = 2;
    pa[1] = 3;
    while (n < top){
        int div = 5;
        int divinc = 2;
        int p = 1;
        //check if number is prime
        //check divisiblity from any possible prime up to the square root of n
        //first hardcode 2 and 3
        if(n%2==0||n%3==0)
            p = 0;
        else{
            while(div<=sqrt(sq)){
                if(n%div==0){
                    p = 0;
                    break;
                }else{
                    div = div + divinc;
                    if(divinc==2) divinc = 4; else divinc = 2;
                }
            }if(p!=0){ //if it's a prime - 0 is not, 1 is prime
                total = total + n;
                np++;
                pa[np] = n;
                //cout << np << " prime number: " << n << endl; //takes too long if it prints everything
            }
        }
        n += inc;
        if(inc==2) inc = 4; else inc = 2;
    }
    for (int c=0;c<=np;c++){
        atotal += pa[c];
    }
    cout << "Total " << top << ": " << total << endl;
    cout << "Array total: " << atotal << endl;
    cout << "Elapsed time: " << clock() << " " << CLOCKS_PER_SEC << "s of a second" << endl << endl;
    while(true){
            int ptoview = 0;
            cout << "Enter the number of the prime you would like to see (you can view every prime number below "<<top<<") ";
            cin >> ptoview;
            if (pa[ptoview-1]){
                if (pa[ptoview-1] < top)
                    cout << ptoview << " prime: " << pa[ptoview-1] << endl;
                else
                    cout << "Too high/low" << endl;
                cout << endl;
            }
        }
    system("PAUSE");
    return 0;
}

Ответы [ 2 ]

3 голосов
/ 26 февраля 2011

Вот подсказка как минимум к одной проблеме. Посмотрите, что происходит при замене: 

for (int c=0;c<=np;c++){
    atotal += pa[c];
}

с: 

for (int c=0;c<=np;c++){
    bignum oldatotal = atotal;
    atotal += pa[c];
    if (atotal < oldatotal)
        cout << "Hmmm: " << oldatotal << " " << atotal << endl;
}

Я получаю что-то вроде: 

Hmmm: 4294819625 12858
Hmmm: 4294864122 123849
Hmmm: 4294717053 27802
Hmmm: 4294697657 51420
: : :
Hmmm: 4293781002 792849
Hmmm: 4294658253 1676602
Hmmm: 4293686116 710941
Hmmm: 4294706293 1737578
Total 2000000: 947402457
Array total: 947402457

Я не буду вдаваться в подробности, так как это головоломка, и я предполагаю, что вы хотите, чтобы она была хоть немного сложнее: -)

И да, вы правы (основываясь на вашем комментарии ниже), поэтому я сделаю ответ немного менее тупым, чтобы он был более полезным для других.

Тип unsigned long недостаточно велик, чтобы содержать сумму всех этих простых чисел, поэтому он оборачивается.

Может ли он содержать фактические простые числа, я не проверял, но ответ в следующем параграфе также решит это.

Возможно, вы захотите попробовать переопределить bignum как «больший» тип, например unsigned long long, если он доступен.

2 голосов
/ 26 февраля 2011

Не смотрится на все, но sq не изменяется в основном цикле while.Это не кажется правильным.(Кстати, я бы использовал ситовый фильтр, чтобы добраться до простых чисел).

...