Праект Эйлера 10: просты код не дае жаданага выніку, трэба дапамагчы зразумець, чаму

Я рашэнне задач праекта Эйлера для пінкоў, я ў цяперашні час пад нумарам 10.

Перш за ўсё: <�моцны> Я ведаю, што ёсць і іншыя рашэнні , я зараз пішу <�моцны> іншы метад з дапамогай рэшата Эратасфена. <�Моцны> Тое, што я хацеў бы ваша дапамога ў разуменні таго, чаму гэты код не працуе .

Гэта мой код (праблемы заключаецца ў знаходжанні сумы кожнага простага ліку да 2 млн). Метад просты праверкі, здаецца, працуе добра, але вынік значна менш, чым павінна быць.

class Euler10
{
    public static void Main()
    {
        long sum = 0;//Was originally an int. Thanks Soner Gönül!
        for(int i = 1; i < 2000000; i++) 
        {
            if (CheckIfPrime(i) == true)
                sum += i;
        }
        System.Console.WriteLine(sum);
        System.Console.Read();
    }

    static bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;

        for (int i = 3; i*i < number; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }
}

Нумар я атрымліваю 1308111344, што на два парадку менш, чым павінна быць. Код настолькі просты, я збіты з панталыку тым памылкі.

EDIT: making sum a long solved the digit problem, thanks everyone! Now, though, I get 143042032112 as an answer: the i*i in CheckIfPrime() isn't always right. Using the sqrt() function and adding one (to compensate for the int cast) gives the correct result. Here's the correct CheckIfPrime() function:

 bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;
        int max = 1 + (int)System.Math.Sqrt(number);
        for (int i = 3; i < max; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }

EDIT 2: Will Ness helped me optimize the code further (calculating number's square root and comparing it to i is slower than elevating i^2 and then comparing it to number): the problem with the original method is that it didn't take into consideration edge cases in which number is the exact square of i, thus sometimes returning true instead of false. The correct code for CheckIfPrime(), then, is:

bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;

        for (int i = 3; i*i <= number; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }

Яшчэ раз дзякуй людзі!

3
Як ужо адзначалася, вы перавышаючы межы 32 бітнай арыфметыкі. Дзве рэчаў, каб разгледзець наступныя пытанні: па-першае, разгледзець пытанне аб выкарыстанні правяраецца арыфметыкі; хоць гэта павольней, вы б знайшлі сваю памылку адразу. Па-другое, ёсць праблемы Эйлера, якія выходзяць за межы 64-бітнай арыфметыкі; разгледзець пытанне аб выкарыстанні BigInteger. Гэта павольней, але ён не мае якіх-небудзь асаблівых мяжа яго арэала. (У выпадку, калі вам трэба адвольна дакладныя рацыянальныя для якой-небудзь прычыны, Solver Foundation Microsoft мае Rational класа, гэта бясплатна.)
дададзена аўтар Eric Lippert, крыніца
Як ужо адзначалася, вы перавышаючы межы 32 бітнай арыфметыкі. Дзве рэчаў, каб разгледзець наступныя пытанні: па-першае, разгледзець пытанне аб выкарыстанні правяраецца арыфметыкі; хоць гэта павольней, вы б знайшлі сваю памылку адразу. Па-другое, ёсць праблемы Эйлера, якія выходзяць за межы 64-бітнай арыфметыкі; разгледзець пытанне аб выкарыстанні BigInteger. Гэта павольней, але ён не мае якіх-небудзь асаблівых мяжа яго арэала. (У выпадку, калі вам трэба адвольна дакладныя рацыянальныя для якой-небудзь прычыны, Solver Foundation Microsoft мае Rational класа, гэта бясплатна.)
дададзена аўтар Eric Lippert, крыніца
Нарэшце, ёсць шмат спосабаў зрабіць вашу асноўную праверку хутчэй. Напрыклад, вы можаце паскорыць яго значным фактарам, правяраючы на ​​2 і 3, а затым для (INT I = 6; я * я <�лік; I + = 6) {калі ((нумар% (я - 1) == 0 || лік% (г + 1) == 0) Такім чынам, вы праверкі на дзелім на 5, 7, 11, 13, 17, 19, ... і пропуск праверкі 4 , 6, 8, 9, 10, 12, 14, 15, 16, ... замест таго, што вы робіце, які проста прапускаючы 4, 6, 8, 10, 12, 14, ... няма неабходнасці праверыць любы лік, якое дзеліцца на тры ўжо, так як вы ўжо праверылі.
дададзена аўтар Eric Lippert, крыніца
Гэта не рэшата Эратасфена, вы толькі тэставанне простых лікаў з дапамогай пробнага дзялення.
дададзена аўтар starblue, крыніца

10 адказы

Ваш код не працуе, таму што ён спрабуе з дапамогай 32-бітнага кода <> Int ўтрымліваць лік, якое перавышае максімальнае значэнне ў зменнай з 32-бітным. Адказ на праблемы 142913828922 , які мае патрэбу ў 38 біт.

Змена тыпу дадзеных Сума на доўгі павінен вырашыць гэтую праблему.

3
дададзена
Спойлеры, цукерка!
дададзена аўтар Eight-Bit Guru, крыніца
@MatthewWatson якім чынам адліваная прадухіліць SO? ня я проста спыніць б павялічваючы пры дасягненні 32-бітнае значэнне, як робіць суму?
дададзена аўтар Christian Fratta, крыніца

Ваш код не працуе, таму што ён спрабуе з дапамогай 32-бітнага кода <> Int ўтрымліваць лік, якое перавышае максімальнае значэнне ў зменнай з 32-бітным. Адказ на праблемы 142913828922 , які мае патрэбу ў 38 біт.

Змена тыпу дадзеных Сума на доўгі павінен вырашыць гэтую праблему.

3
дададзена
Спойлеры, цукерка!
дададзена аўтар Eight-Bit Guru, крыніца
@MatthewWatson якім чынам адліваная прадухіліць SO? ня я проста спыніць б павялічваючы пры дасягненні 32-бітнае значэнне, як робіць суму?
дададзена аўтар Christian Fratta, крыніца

Вы карыстаецеся Int для < код> сума зменная, 32-біт , але вы паспрабуйце надаць яму больш, чым Int32.Maximum які 2147483647 .

Але ваш вынік 143042032112 , які мае патрэбу ў большай колькасці бітаў, чым 32 для захавання яго.

Усталюйце яго тып доўгай які крамы 64 біт.

long sum = 0;

Тут працуе DEMO .

2
дададзена

Вы карыстаецеся Int для < код> сума зменная, 32-біт , але вы паспрабуйце надаць яму больш, чым Int32.Maximum які 2147483647 .

Але ваш вынік 143042032112 , які мае патрэбу ў большай колькасці бітаў, чым 32 для захавання яго.

Усталюйце яго тып доўгай які крамы 64 біт.

long sum = 0;

Тут працуе DEMO .

2
дададзена

for (... i=3 ; i*i < number; i+=2 ) is wrong. It should be

for (... i=3 ; i*i <= number; i+=2 )
 ...

і я і нумар павінен быць таго ж тыпу, вядома; гэта амаль ніколі не дасць вам перапаўненне, так як вы пачынаеце з 3 <�суб> (калі нумар вельмі вялікі, блізка да верхняй мяжы дыяпазону тыпу по) </суб>.

Параўнанне павінна быць уключана злавіць выпадкі, калі нумар з'яўляецца квадратам простага.

2
дададзена
«Гэта ніколі не дасць вам перапаўненне, так як вы пачынаеце з 3» <�я> і мяжа досыць малы . Вы можаце атрымаць перапаўненне, калі мяжа быў блізкі да ліміту тыпу. [Я ведаю, што вы ведаеце, што, але гэта павінна быць сказана для паўнаты карціны.]
дададзена аўтар Daniel Fischer, крыніца

for (... i=3 ; i*i < number; i+=2 ) is wrong. It should be

for (... i=3 ; i*i <= number; i+=2 )
 ...

і я і нумар павінен быць таго ж тыпу, вядома; гэта амаль ніколі не дасць вам перапаўненне, так як вы пачынаеце з 3 <�суб> (калі нумар вельмі вялікі, блізка да верхняй мяжы дыяпазону тыпу по) </суб>.

Параўнанне павінна быць уключана злавіць выпадкі, калі нумар з'яўляецца квадратам простага.

2
дададзена
«Гэта ніколі не дасць вам перапаўненне, так як вы пачынаеце з 3» <�я> і мяжа досыць малы . Вы можаце атрымаць перапаўненне, калі мяжа быў блізкі да ліміту тыпу. [Я ведаю, што вы ведаеце, што, але гэта павінна быць сказана для паўнаты карціны.]
дададзена аўтар Daniel Fischer, крыніца

Выкарыстанне доўга павінна дапамагчы. http://msdn.microsoft.com/en-us/ бібліятэка/ctetwysk.aspx Дае 64 разраднае цэлы лік, дзе ў якасці ИНТ толькі 32 біта.

2
дададзена

Выкарыстанне доўга павінна дапамагчы. http://msdn.microsoft.com/en-us/ бібліятэка/ctetwysk.aspx Дае 64 разраднае цэлы лік, дзе ў якасці ИНТ толькі 32 біта.

2
дададзена

Ваш алгарытм не рэшата Эратасфена; аператар па модулю дае яго. Ваш алгарытм пробнае дзяленне на няцотных чыслах. Вось функцыя, з дапамогай рэшата Эратасфена:

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

Выклік sumPrimes (2000000) дае адказ, які я не буду запісваць з павагі да Project Euler. Гэтая функцыя працуе падчас O (<�ет> п Часопіс Часопіс <�ет> п ), што нашмат лепш, чым O (<�ет> п ^ 2) з крынічнай праграмы , Ёсць больш эфектыўныя спосабы рэшата, але гэта проста, і лёгка атрымаць права, і дастаткова добра для большасці мэтаў, уключаючы ваш. Вы павінны атрымаць адказ менш чым за секунду.

Я пакіну гэта вам перавесці C# з адпаведнымі тыпамі дадзеных.

Калі вы зацікаўлены ў некалькі большай версіі гэтай праблемы, я падлічыў, сума першага мільярда простых лікаў ў маім блогу: 11138479445180240497.

1
дададзена
Я ведаю, што гэта не рэшата, што я меў на ўвазе, што я працаваў на сіце ў іншым файле (я хацеў бы ведаць, чаму гэты код не працуе, не тое, што ёсць больш эфектыўны спосаб вырашыць гэтую праблему). Вялікі дзякуй за адказ, я вызначана праверка PP-за!
дададзена аўтар Christian Fratta, крыніца

Ваш алгарытм не рэшата Эратасфена; аператар па модулю дае яго. Ваш алгарытм пробнае дзяленне на няцотных чыслах. Вось функцыя, з дапамогай рэшата Эратасфена:

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

Выклік sumPrimes (2000000) дае адказ, які я не буду запісваць з павагі да Project Euler. Гэтая функцыя працуе падчас O (<�ет> п Часопіс Часопіс <�ет> п ), што нашмат лепш, чым O (<�ет> п ^ 2) з крынічнай праграмы , Ёсць больш эфектыўныя спосабы рэшата, але гэта проста, і лёгка атрымаць права, і дастаткова добра для большасці мэтаў, уключаючы ваш. Вы павінны атрымаць адказ менш чым за секунду.

Я пакіну гэта вам перавесці C# з адпаведнымі тыпамі дадзеных.

Калі вы зацікаўлены ў некалькі большай версіі гэтай праблемы, я падлічыў, сума першага мільярда простых лікаў ў маім блогу: 11138479445180240497.

1
дададзена
Я ведаю, што гэта не рэшата, што я меў на ўвазе, што я працаваў на сіце ў іншым файле (я хацеў бы ведаць, чаму гэты код не працуе, не тое, што ёсць больш эфектыўны спосаб вырашыць гэтую праблему). Вялікі дзякуй за адказ, я вызначана праверка PP-за!
дададзена аўтар Christian Fratta, крыніца