C# For loop producing index out of range error

Question

I am trying to solve the Project Euler challenge 46. In this challenge, you have to find the first composite number that cannot be made by the sum of a prime and twice a square.

To solve the problem, I am looping through all odd numbers, checking whether they are prime and if they aren't, looping through all the primes below the number to check if the difference is twice a square.

I am doing this using two for loops and for some reason, the for loop that loops through the primes is throwing an Argument Out Of Range Exception.

I have no idea why this error is being thrown, as the for loop shouldn't allow for this to happen.

My Code:

using System;
using System.Collections.Generic;

namespace Challenge_46
{
    class Program
    {
        /*
         * Task -
         * It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
         * 9 = 7 + 2 × 1^2
         * 15 = 7 + 2 × 2^2
         * 21 = 3 + 2 × 3^2
         * 25 = 7 + 2 × 3^2
         * 27 = 19 + 2 × ^22
         * 33 = 31 + 2 × 1^2
         * 
         * It turns out that the conjecture was false.
         * 
         * What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
         */
        static void Main(string[] args)
        {
            List<int> primes = new List<int>() { 3 }; // We do not need 2 been as an odd number minus an even number is odd, which cannot be 2 times a square
            bool notFound = true;

            for (int i = 5; notFound == true; i += 2 )
            {
                if (IsPrime(i, primes))
                {
                    primes.Add(i);
                    continue;
                }

                for (int j = 0; primes[j] < i && j < primes.Count; j++)
                {
                    if (!(IsSquare( (i - primes[j]) / 2)))
                    {
                        notFound = false;
                    }
                    else
                    {
                        notFound = true;
                        break;
                    }
                }

                if (notFound == false)
                {
                    Console.WriteLine("The first composite number that cannot be written as the sum of a prime and twice a square is {0}", i);
                }
            }
        }

        static bool IsSquare(int n)
        {
            if (Math.Sqrt(n) == Math.Floor(Math.Sqrt(n))) // if the square root is an integer
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        static bool IsPrime(int n, List<int> primes)
        {
            foreach (int prime in primes)
            {
                if (n % prime == 0)
                {
                    return false;
                }
            }

            return true;
        }
    }
}

Help would be much appreciated.

Thanks in advance.

I think primes[j] < i && j < primes.Count should be the other way around. First check that j is in the right range, then check prime[j] ( && short circuit will ensure this will work) — Stefan, Jun 29 '19 at 20:57
&&` _is_ short-circuit but it is also evaluating left-to-right. — H H, Jun 29 '19 at 20:59
Thanks, this fixed the problem. In the future, I will remember to check the value of something before using it in a list / array. — BenWornes, Jun 30 '19 at 15:05

score 4 · Accepted Answer · answered Jun 29 '19 at 21:00

Your mistake is caused by the order of the evaluations of your exit in the for condition. The conditions are evaluated from left to right, so the code is first evaluating the condition primes[j] < i and only after that the code checks if j < primes.Count but this will not protect the first evaluation to going out of range when j is equal to primes.Count.

The fix is easy, just swap the two conditions. First check if you are still inside the range then check for the other condition

for (int j = 0; j < primes.Count && primes[j] < i; j++)

Thanks for this, the change in order worked. Now that I think about it, it does make more sense to check how large J is before checking its corresponding index value in primes. Thanks. — BenWornes, Jun 30 '19 at 00:38

C# For loop producing index out of range error

1 Answers1