Как найти наибольшую сумму делителей числа между 2 и N? - PullRequest
Новая
       33

Как найти наибольшую сумму делителей числа между 2 и N?

0 голосов
/ 07 декабря 2018

У меня простая математическая задача.Я хочу найти число в диапазоне [2,N] (исключая 1 и N из делителей) с наибольшей суммой делителей.Например, для N = 100 число с наибольшей суммой делителей между 2 и 100 равно 96, а сумма всех его делителей равна 155.

Я написал следующую программу, чтобы показать мне суммуиз делителей этого числа, но не мог понять, как получить это число сам.Как мне найти и напечатать это число? 

int main(int argc, char const *argv[])
{
    int N,
        sum,
        max=0;

    scanf("%d", &N);

    int i = 0,
        d = 0;
    for(i=2; i<=N; i++)
    {
        sum=0;
        for(d = 2; d < i; d++)
        {
            if(i % d == 0)
            {
                sum += d;
            }
        }

        if(sum > max)
        {
            max = sum;
        }

    }
    printf("%d\n", max);


    return 0;
}

Ответы [ 3 ]

0 голосов
/ 07 декабря 2018

Когда вы сохраняете max, вам просто нужно сохранить копию i в отдельной переменной.

Вот рабочая программа: 

#include <stdio.h>

int
main(int argc, char const *argv[])
{
    int N,
     sum,
     max = 0;
    int max_i = -1;

    printf("Enter N: ");
    fflush(stdout);

    scanf("%d", &N);

    int i = 0,
        d = 0;

    for (i = 2; i <= N; i++) {
        sum = 0;
        for (d = 2; d < i; d++) {
            if (i % d == 0) {
                sum += d;
            }
        }

        if (sum > max) {
            max = sum;
            max_i = i;
        }

    }

    printf("MaxSum:%d Index:%d\n", max, max_i);

    return 0;
}

Вот вывод: 

MaxSum:155 Index:96
0 голосов
/ 07 декабря 2018

Другие хорошо показали, как сохранять и сообщать i, при котором достигнут максимум.

И все же я хотел добавить, как подход OP может быть значительно быстрее: итерация доквадратный корень из N, а не N.Этот способ примерно в квадратный-корень (N) раз быстрее.Не так важно, когда N равно 100, но важно для больших. 

#include <stdlib.h>
#include <stdio.h>

void print_maxsumdiv(int N, int mode) {
  unsigned long long loop_count = 0;
  int sum, max = 0;
  int max_i = 0;
  int i = 0, d = 0;
  for (i = 2; i <= N; i++) {
    sum = 0;

    if (mode) {
      // Iterate up to the just under the square root of `i`
      for (d = 2;  d < i/d; d++) {
        loop_count++;
        if (i % d == 0) {
          sum += d + i/d;  // Add both dividers
        }
      }
      if (d == i/d) {  // perfect square
        sum += d;
      }
    }
    else {
      // Iterate up `i`  (OP's original approach)
      for (d = 2;  d < i; d++) {
        loop_count++;
        if (i % d == 0) {
          sum += d;
        }
      }
    }

    if (sum > max) {
      max = sum;
      max_i = i;
    }

  }
  printf("i:%6d max:%9d (count:%12llu)\n", max_i, max, loop_count);
}

int main() {
  for (int mode = 0; mode < 2; mode++) {
    print_maxsumdiv(100, mode);
    print_maxsumdiv(10000, mode);
    //print_maxsumdiv(1000000, mode);
  }
  return 0;
}

Вывод 

i:    96 max:      155 (count:        4851)
i:  9240 max:    25319 (count:    49985001)
i:    96 max:      155 (count:         480)
i:  9240 max:    25415 (count:      646800)
0 голосов
/ 07 декабря 2018

Это должно быть легко.Просто введите еще одну переменную valueForMax 

int N,
    sum,
    max=0,
    valueForMax = 0;

и обновите ее вместе с max

    if(sum > max)
    {
        valueForMax = i;
        max = sum;
    }

Тогда вы сможете 

printf("best value %d, sum = %d\n", valueForMax, max);
...