Сумма чисел до 10 000, кратных 3, 5 или 7 в Java

Question

Я знаю, как заставить программу складывать суммы кратных для каждого из 3, 5 и 7, но я не уверен, как заставить программу использовать каждое число только один раз. Например, я могу заставить программу узнать все числа и сложить их для 3, а затем сделать то же самое для 5, но тогда число 15 будет в конечном числе дважды. Я не уверен точно, как я могу получить это, чтобы взять номер только один раз. Спасибо за любую помощь.

Answer 1

Хотя подход генерации и тестирования прост для понимания, он также не очень эффективен, если вы хотите использовать его для больших чисел. Вместо этого мы можем использовать принцип включения-исключения .

Идея состоит в том, чтобы сначала сложить слишком много чисел, посмотрев на коэффициенты 3, 5 и 7 по отдельности. Затем мы вычитаем те, которые мы сосчитали дважды, то есть, кратные 3 * 5, 3 * 7 и 5 * 7. Но теперь мы вычли слишком много и нам нужно снова добавить кратные 3 * 5 * 7.

Начнем с нахождения суммы всех целых чисел 1..n, кратных k. Сначала мы узнаем, сколько их, m = n / k, округляется в меньшую сторону благодаря целочисленному делению. Теперь нам нужно просто подытожить последовательность k + 2*k + 3*k + ... + m*k. Мы выделяем k и получаем k * (1 + 2 + ... + m).

Это хорошо известный арифметический ряд, который, как нам известно, суммируется с k * m * (m + 1)/2 (см. номер треугольника ).

private long n = 9999;
private long multiples(long k) {
    long m = n / k;
    return k * m * (m + 1) / 2:
}

Теперь мы просто используем включение-исключение, чтобы получить окончательную сумму:

long sum = multiples(3) + multiples(5) + multiples(7)
         - multiples(3*5) - multiples(3*7) - multiples(5*7)
         + multiples(3*5*7);

Это будет намного лучше масштабироваться до большего n, чем просто зацикливание всех значений, но остерегайтесь переполнения и при необходимости измените на BigInteger с.

Answer 2

Самый простой подход - использовать цикл for таким образом:

int sum = 0;
for(int i=1; i<10000; i++)
{
    if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
        sum += i;
}

Answer 3

для решения с циклом от 1 до 1000 используйте i <= 10000, иначе оно пропустит само 10000, кратное 5. Извинения, по некоторым причинам я не могу опубликовать это как комментарий </p>

Answer 4

Одним из простых решений было бы добавить каждое число, кратное 3,5 или 7, в список ответов. И затем, когда вы работаете через каждый номер, убедитесь, что его нет в списке ответов.

(псевдокод)

List<int> AnswerList;
List<int> MultiplesOfFive;
List<int> MultiplesOfSeven;
List<int> MultiplesOfThree;

for (int i = 0 ; i < 10000; i++)
{
  if ( i % 3 == 0 && AnswserList.Contains(i) == false)
  {
    MultiplesOfThree.Add(i); 
    AnswerList.Add(i);
  }
  if ( i % 5 == 0 && AnswserList.Contains(i) == false)
  {
    MultiplesOfFive.Add(i); 
    AnswerList.Add(i);
  }
  if ( i % 7 == 0 && AnswserList.Contains(i) == false)
  {
    MultiplesOfSeven.Add(i); 
    AnswerList.Add(i);
  }
}

Answer 5

Я бы использовал Set . Таким образом, вы гарантированно не получите дубликатов, если они являются вашей основной проблемой.

Answer 6

Используйте Set для хранения уникальных кратных значений, а затем суммируйте значения Set.