Project euler number 10#

Question

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

And my answer is:

bool IsRishoni;
int soap = 0;
for (int i = 3; i < 2000000; i++)
{
    IsRishoni = true;
    for (int a = 2; (a <= Math.Sqrt(i)) && (IsRishoni); a++)
    {
        if (i % a == 0)
            IsRishoni = false;
    }
    if (IsRishoni)
    {
        soap = i + soap;
    }
}
Console.WriteLine(soap + 2);
Console.ReadLine();

Why is this not working? the answer I got is 1179908154 ... help please.

He doesn't know the answer yet (that's the problem he is trying to solve!), I won't spoil it but the answer is < 100000 — Ian G, Apr 28 '12 at 08:02

score 6 · Accepted Answer · edited May 23 '17 at 12:11

6

Replace

soap = i + soap;

with

soap = checked(i + soap);

..and the problem should be exposed.

This question has more details: No overflow exception for int in C#?

edited May 23 '17 at 12:11

Community

1
1

answered Apr 28 '12 at 08:11

Anders Lindahl

41,582
9
89
93

2

Um, the problem is described in that question you've been given a link to. Have you read it? – Alexey Frunze Apr 28 '12 at 08:27
1

I think the point of Euler problems is to hands-on experience various aspects of computing, so I'm not gonna tell you precisely what the problem is. Try out the change above, and continue from there. – Anders Lindahl Apr 28 '12 at 08:35

Ian G · Answer 2 · 2012-04-28T08:50:02.890

2

Your answer (stored in soap) is a value greater than int.Maxvalue (2,147,483,647).

Your answer is ~ 150,000,000,000

In other words you need to use an data type which is bigger than that.

long.MaxValue = 9,223,372,036,854,775,807
int.Maxvalue = 2,147,483,647

edited Apr 28 '12 at 08:50

answered Apr 28 '12 at 08:05

Ian G

29,468
21
78
92

Douglas · Answer 3 · 2012-04-28T08:50:28.757

The result you’re after might be too large to represent through a 32-bit signed integer (int).

Let’s first determine the result’s upper bound by assuming that all numbers are prime. Through summation, we know that the sum of all numbers up to N (inclusive) is N * (N + 1) / 2; thus, the upper bound for the sum of all primes up to 2,000,000 is 2,000,001,000,000. This is larger than the maximum value allowed by int, 2,147,483,647, so you’re probably getting a numeric overflow which is silently ignored.

If you wanted a more accurate estimate of your answer, you could use the prime number theorem, which states that the probability of a random integer between 0 and N being prime is approximately 1 / ln(N). Combining this with our previous formula, the approximate sum of all primes up to N is N * (N + 1) / (2 * ln(N)). For 2,000,000, this evaluates to around 138,000,000,000, which is still larger than the maximum value for int.

To resolve your problem, you could simply switch the integral data type you’re using for the soap variable to a 64-bit integer representation, such as long. Its maximum value is 9,223,372,036,854,775,807, so it would definitely be able to represent your number.

long soap = 0;

On a separate note: Since you’re working with sequences of primes, you could achieve a huge performance gain (at least 100×) if you change your implementation to a Sieve of Eratosthenes.

Project euler number 10#

3 Answers3