Делители треугольных чисел (Эйлер 12)

Question

Я нашел несколько тем, связанных с этой самой проблемой, я просто хочу знать, почему мой код возвращает неверные данные. Таким образом, мы должны найти первое число треугольника, имеющее более 500 делителей. Подробности можно найти здесь: http://projecteuler.net/problem=12 А вот мой код:

Int64 triangularnum = 1;
            for (Int64 num = 2; num > 0; num++)
            {
                if(has501Divisors(triangularnum))
                {
                    MessageBox.Show(triangularnum.ToString());
                    break;
                }
                triangularnum += num;
            }



private bool has501Divisors(Int64 candidate)
        {
            bool has501 = false;
            int count = 0;
            for (int i = 1; i < Math.Sqrt(candidate); i++)
            {
                if (candidate % i == 0) count += 1;
                if (count > 501)
                {
                    return true;
                }
            }
            return has501;
        }

Это дает мне номер 842161320, который, по-видимому, неверно.

Answer 1

Вы должны увеличить свой count номер по 2 не 1,

Также ваш

if (count > 501)

часть неверна, потому что ваша граница должна 500 не 501, Измените это на count > 500 вместо.

static void Main(string[] args)
{
    Console.WriteLine(Find());
}

public static int Find()
{
    int number = 0;
    for (int i = 1; ; i++)
    {
        number += i; // number is triangle number i
        if (CountDivisorsOfNumber(number) > 500)
            return number;
    }
}


private static int CountDivisorsOfNumber(int number)
{
     int count = 0;
     int end = (int)Math.Sqrt(number);
     for (int i = 1; i < end; i++)
     {
         if (number % i == 0)
             count += 2;
     }
     if (end * end == number) // Perfect square
         count++;
     return count;
}

Это печатает 76576500 и выглядит как правильное решение.

Answer 2

Проблема в том, что вы ограничиваете свой цикл квадратным корнем, что разумно, однако это означает, что вам нужно увеличить счетчик на два, а не на 1, чтобы учесть оба делителя.

Измените приращение на это:

if (candidate % i == 0) count += 2;

Кроме того, проверка вашего счета проверяет наличие более 501 делителей, а не 500.

Answer 3

Быстрый просмотр, но ваш чек не в порядке:

if (count > 501)

Это остановится на счете 502, а не 501.

---

for (int i = 1; i < Math.Sqrt(candidate); i++)

9 делится на 3, поэтому вы должны использовать <= здесь. Кроме того, вы делите на 1, вы должны начать с i = 2.