Проект Эйлера # 21

Question

Состояние:

Пусть д (п) определяется как сумма собственных делителей п (числа меньше, чем п, которые делят равномерно на п). Если d (a) = b и d (b) = a, где a ≠ b, то a и b являются дружественной парой, и каждый из a и b называется дружественным числом.

Например, правильные делители 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110; поэтому d (220) = 284. Собственные делители 284 равны 1, 2, 4, 71 и 142; так d (284) = 220.

Вычислить сумму всех дружественных чисел под 10000.

я сделал следующее:

static void Main() 
    { 
     long sum = 0; 
     List<int> passedValues = new List<int>(); 
     for (int i = 1; i < 10000; i++) 
     { 
      var number1 = SumOfNumber(i); 
      var number2 = SumOfNumber(SumOfNumber(i)); 
      if (number2 == i && !passedValues.Contains(number1)) 
      { 
       sum = sum + number1; 
       passedValues.Add(number1); 
       passedValues.Add(number2); 
      } 
     } 
     Console.WriteLine(sum); 
     Console.ReadKey(); 
    } 

    private static int SumOfNumber(int input) 
    { 
     int sum = 0; 
     for (int i = 1; i <= input/2; i++) 
     { 
      if (input%i == 0) 
      { 
       sum += i; 
      } 
     } 
     return sum; 
    } 

однако это дает результат 40284 в то время как правильный ответ Кажется, 31626 почему моя программа работает неправильно? Я добавляю что-то несколько раз? Я также попытался добавить список хранить переданные значения, однако в конечном итоге дает результат 25008:

static void Main() 
    { 
     long sum = 0; 
     List<int> passed = new List<int>(); 
     for (int i = 1; i < 10000; i++) 
     { 
      var number1 = SumOfNumber(i); 
      var number2 = SumOfNumber(SumOfNumber(i)); 
      if (number2 == i && !passed.Contains(i)) 
      { 
       sum = sum + number1; 
       passed.Add(number1); 
      } 
     } 
     Console.WriteLine(sum); 
     Console.ReadKey(); 
    } 

Answer 1

Есть две проблемы:

1. Вы не добавляющие как дружные номера пары к сумме.
2. Вы включаете в себя идеальные числа (где d (n) = n), которые не квалифицируются как дружественные пары, поскольку нарушается ≠ b.

Я думаю, вы были ближе, когда вы не добавили в список для хранения передаваемых чисел, потому что вызвало вопрос # 1 выше, так как вы добавляете только вклад number1 в сумме, но добавление как number1 и number2, в результате чего number2 в конечном итоге будет пропущен. Для решения проблемы № 2 вам также необходимо подтвердить number1 != number2. Например:

if (number2 == i && number1 != number2) 
       ^^^^^^^^^^^^^^^^^^^^^ add this check 
{ 
    sum = sum + i; 

После применения обоих этих исправлений для вашего кода при условии, я получаю ожидаемый итог 31626.

Answer 2

я получил результат, 31626. Разница здесь в том, как предотвратить дубликата в сумма. Вместо сохранения в списке просто убедитесь, что i всегда меньше числа 1.

static void Main() 
    { 

     long sum = 0; 
     List<int> passedValues = new List<int>(); 
     for (int i = 1; i < 10000; i++) 
     { 
      var number1 = SumOfNumber(i); 
      var number2 = SumOfNumber(SumOfNumber(i)); 


      if (number2 == i && i < number1) 
      { 
       sum = sum + i + number1; 

      } 
     } 
     Console.WriteLine(sum); 
     Console.ReadKey(); 
    } 

    private static int SumOfNumber(int input) 
    { 
     int sum = 0; 
     for (int i = 1; i <= input/2; i++) 
     { 
      if (input % i == 0) 
      { 
       sum += i; 
      } 
     } 
     return sum; 
    } 

Answer 3

private static int SumOfNumber(int input) 
{ 
    int sum = 0; 
    for (int i = 1; i <= input/2; i++) 
    { 
     if (input%i == 0) 
     { 
      sum += i; 
     } 
    } 
    return sum; 
} 

Это не правильно. Вы добавляете только один из факторов, а не зацикливаетесь на sqrt этого числа.