CODEWITHSUNDEEP
c#primes
phcoding
phcoding

Reputation: 608

Sum of primes for large numbers

I've been working on this problem for some time now and I can't figure out why I keep getting an overflow error.

The code works fine to a point then doesn't work for larger values. I have tested it and found the the breaking point to be the input 225287 (with the last non-breaking value being 225286, which gives an output of 2147431335).

How can I get this to work for 2,000,000?

class SumOfPrimes{

static void Main(string[] args)
    {

        Primes primes = new Primes(2000000);         
        Console.WriteLine(primes.list_of_primes.Sum());
        Console.ReadLine();
    }

  }

class Primes
{
    public HashSet<int> all_numbers = new HashSet<int>();
    public HashSet<int> list_of_primes = new HashSet<int>();
    public HashSet<int> list_of_nonprimes = new HashSet<int>();


    public Primes(int n)
    {
        all_numbers = new HashSet<int>(Enumerable.Range(1, n));
        for (int i = 2; i < Math.Sqrt(n) + 1; i++)
        {
            for (int j = 3; j <= n / i; j++)
                list_of_nonprimes.Add(i * j);
        }
        list_of_primes = new HashSet<int>(all_numbers.Except(list_of_nonprimes));
    }
 }

Upvotes: 0

Views: 421

Answers (2)

michaelb958--GoFundMonica
michaelb958--GoFundMonica

Reputation: 4708

What's happening is an integer overflow. On 32-bit systems, int can only hold positive values up to 2^31-1 (2147483647). You could try using a 64-bit integer (I think C# has them), or find an arbitrary-size integer library (@Calpis helpfully linked to a built-in one).

Upvotes: 1

masotann
masotann

Reputation: 911

the values you have doesn't fit in a memory the size of an int, so try using biginteger used on the website here.

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx

Upvotes: 2

Related Questions