Limit of Graph reached

Question

I need to find the sum of primes below two million, but limit of graph reached at 110002. What is limit of graph and how to avoid it.

public class Prime
{
    private List<long> primes=new List<long>() {2,3,5,7,11};

    public void prime()
    {
        long limit=150000;
        long sum=0;
    
        for(long i=2;i<=limit;i++)
        {
            if(isPrime(i))
            {
                primes.Add(i);
            }       
        }
        sum = primes.Sum();
        Console.WriteLine(sum);
    }
        
    private static bool isPrime(long num)
    {
        Prime pa=new Prime();
        Console.WriteLine("Checking for: "+num);
        foreach(long j in pa.primes)
        {
            if(num%j==0)
            {
                return false;
            }
        }
        return true;
    }
}

Answer 1

When working with millions it's a very time to think on efficiency:

1. You don't want to create Prime instances at all, let alone millions
2. Hardcoded long limit=150000; looks very suspicious
3. Both loops are inefficient
4. Let's get rid of slow UI Console.WriteLine until the very end

Let's enumetare primes with a help of a sieve:

  private static IEnumerable<long> AllPrimes() {
    // Special case: there's only one even prime number         
    yield return 2;

    List<long> knownPrimes = new List<long>(1_000_000);

    for (long p = 3; ; p += 2) {
      // if p is not prime, 
      // the smallest non-trivial divisor is less or eqaul to Sqrt(p)
      long upTo = (long) (Math.Sqrt(p) + 0.5);

      bool isPrime = true;

      foreach (long divisor in knownPrimes)
        if (p % divisor == 0) {
          isPrime = false;

          break;
        }
        else if (divisor > upTo) // we don't want to scan all known primes
          break;

      if (isPrime) {
        knownPrimes.Add(p);

        yield return p;
      }
    }    
  }

Time to query the AllPrimes() method with a help of Linq:

  long result = AllPrimes()
    .TakeWhile(p => p < 2_000_000)
    .Sum();

  Console.Write(result);

Outcome:

  142913828922

Answer 2

You shouldn't be creating a new Prime() every time you call isPrime(). By doing that, you are breaking the isPrime() calculation because it's then not using the list of primes that's being added to.

Instead, it always checks for primes against 2, 3, 5, 7, 11 (only) with the result that any number that's a product of two primes greater than 11 is considered to be a prime.

Instead, do it like this:

public class Prime
{
    private List<long> primes = new List<long>(){
        2,3,5,7,11
    };
    public void prime()
    {
        long limit = 150000;
        long sum = 0;

        for (long i = 2; i <= limit; i++)
        {
            if (isPrime(i))
            {
                primes.Add(i);
            }
        }
        sum = primes.Sum();
        Console.WriteLine(sum);
    }
    private bool isPrime(long num)
    {
        Console.WriteLine("Checking for: " + num);
        foreach (long j in primes)
        {
            if (num % j == 0)
            {
                return false;
            }
        }
        return true;
    }
}

All I did was make isPrime() non-static and removed the use of pa, instead using the primes list field directly.

This produces an answer of 986017447

Also, if you are using any non-standard development applications such as Linqpad, you should state that in the question - since (from other comments) it appears that Linqpad does not support such a large number of output lines. If that is indeed the case, comment out the Console.WriteLine("Checking for: " + num); line to see if that helps.

Answer 3

Limit of graph means that LINQPad output has reached a certain limit. You are simply writing to much to the output window. Run the code outside LINQPad to get rid of it, but please also implement Matthew Watson's answer.