CODEWITHSUNDEEP
c#primes
Christian Fratta
Christian Fratta

Reputation: 294

Project Euler 10: simple code is not giving the desired result, need help understanding why

I'm solving Project Euler problems for kicks, I'm currently at number 10.

First of all: I know there are other solutions, I'm currently writing another method using the sieve of Eratosthenes. What I'd like your help with is understanding why this code does not work.

This is my code (the problems involves finding the sum of every prime under 2 million). The prime-checking method seems to work fine, but the result is way less than it should be. 

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;
    }
}

The number I get is 1,308,111,344, which is two orders of magnitude lower than it should be. The code is so simple I am baffled by this error.

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;
    }

Thanks again people!

Upvotes: 3

Views: 890

Answers (5)

user448810
user448810

Reputation: 17866

Your algorithm is not the Sieve of Eratosthenes; the modulo operator gives it away. Your algorithm is trial division by odd numbers. Here is a function using the Sieve of Eratosthenes:

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

Calling sumPrimes(2000000) gives the answer, which I won't write down out of respect for Project Euler. That function runs in time O(n log log n), which is much better than the O(n^2) of your original program. There are better ways to sieve, but that is simple, and easy to get right, and good enough for most purposes, including yours. You should get an answer in less than a second.

I'll leave it to you to translate to C# with appropriate data types.

If you're interested in a somewhat larger version of this problem, I calculated the sum of the first billion primes at my blog: 11138479445180240497.

Upvotes: 1

Will Ness
Will Ness

Reputation: 71075

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

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

both i and number must be of the same type of course; this will almost never give you an overflow, since you start from 3 (unless number is very big, close to the upper limit of the type's range).

The comparison should be inclusive to catch cases where number is a square of a prime.

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726639

Your code does not work because it tries using a 32-bit int to hold a number that exceeds the highest value in a 32-bit variable. The answer to the problem is 142,913,828,922, which needs 38 bits.

Changing the data type of sum to long should fix this problem.

Upvotes: 3

Soner G&#246;n&#252;l
Soner G&#246;n&#252;l

Reputation: 98750

You are using int for sum variable which is 32-bit but you are try to assign it more than Int32.Maximum which is 2,147,483,647.

But your result is 143,042,032,112 which needs more bits than 32 for storing it.

Set its type as long which stores 64 bit.

long sum = 0;

Here a working DEMO.

Upvotes: 2

Nanda
Nanda

Reputation: 1058

Using long should help.http://msdn.microsoft.com/en-us/library/ctetwysk.aspx Gives you a 64 bit integer where as int is only 32 bits.

Upvotes: 2

Related Questions