Проект Эйлера 1: Найти сумму всех кратных 3 или 5 ниже 1000

Question

Я пытаюсь решить математические задачи с Руби из Project Euler. Здесь - первый, который я попробовал:

Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, мы получаем 3, 5, 6 и 9. Сумма этих кратно 23.

Найдите сумму всех кратных 3 или 5 ниже 1000.

Пожалуйста, помогите мне улучшить мой код.

total = 0

(0...1000).each do |i|
  total += i if (i%3 == 0 || i%5 == 0)
end

puts total

Answer 1

Гораздо быстрее (постоянное время) ответ:

def sum_multiples(multiple, to)
    n = (to-1) / multiple
    n * (n+1) / 2 * multiple
end

irb(main):001:0> sum_multiples(3, 10) + sum_multiples(5, 10) - sum_multiples(15, 10)
=> 23
irb(main):002:0> sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)
=> 233168

Почему это работает?sum_multiples вычисляет сумму, кратную multiple до, но не включая to (это зависит от целочисленного деления).Сначала вычисляется количество суммируемых кратных чисел (n), затем умножается стандартная формула для суммы 1..n = n (n + 1) / 2 на multiple.Используя это, мы можем сложить суммы для кратных 3 и 5. Тогда мы не должны забывать, что некоторые числа кратны и 3 и 5, поэтому мы вычитаем кратные 15 (3 * 5).

Хотя ваш ответ более чем быстр для ограничения этой проблемы (он должен работать примерно на 1 миллисекунду на современном оборудовании), более быстрое решение, такое как предложенное мной, даст результат при очень большомномера.

Answer 2

Ну, во-первых, вы можете пропустить примерно 666 чисел, начиная с 3, увеличивая на 3. Таким образом, вы рассматриваете только кратные 3. Затем выполните второй цикл, начиная с 5, увеличивая на 5. Здесь вы нужно проверить наличие кратных 3 (или пропустить каждое третье сгенерированное число, поскольку так получилось, что они будут кратны 3), так как они суммировались ранее.

Это позволит вам проверить ~ 500 номеров, примерно половину требуемых номеров.

В качестве альтернативы, вы можете посмотреть, можете ли вы вычислить закрытую форму для суммы (в принципе, суммируйте числа от 1 до этажа (max, N), умножьте это на N, сделайте это для обоих ваших Ns (3 5), но тогда вам придется вычесть числа с двойным счетом, но это по сути вычитает то же самое для N = 15).

Answer 3

вот мой подход, который находит i (1, 333) для 3 * k (3,6,9 ...) и (1200) для 5 * k.

• Подсчитайте все делимые на 3 и вычислите сумму
• Подсчитайте все делимые на 5 и вычислите сумму
• Число, кратное 15, следует считать одним

3 * (1 + 2 + 3 + ... + 333) + 5 * (1 + 2 + 3 ..) - 15 * (1 + 2 ...), который можно сформулировать с помощью n * (n + 1) / 2 и это O (1) время, но я реализую свой код с помощью цикла

и вот мой первый код Ruby :)

total = 0

(0...334).each do |i|
   total += i*3 
end

(0...200).each do |i|
   total += i*5 if (i % 3 != 0) 
end

puts total

здесь демо

Answer 4

puts (0..1000).select {|n| n%3==0 || n%5==0}.inject(0) {|s,n| s+=n}

Answer 5

Мне действительно нравится ответ marcog.

Но в любом случае, здесь используется подход, который использует что-то вроде сита Эратосфена .

divisors = [3, 5]
limit = 1000
can_be_divided = Array.new(limit + 1, false)
divisors.each do |d|
  i = d
  while i < limit
    can_be_divided[i] = true
    i += d
  end
end

result = 0
can_be_divided.each_with_index { |v, i| result += i if v }

Мое решение использует O (N) памятии грубый O (D * N), где N - предел, а D - количество делителей.

Он не конкурирует с элегантным математическим решением, но, возможно, вы найдете его интересным.

Я думаю,Преимущество состоит в том, что с увеличением количества делителей математическое решение будет сложнее рассчитать, так как вам нужно работать со знаменателями.В случае [3, 5] это довольно просто - единственный знаменатель равен 15. Но как насчет [3, 5, 7, 11, 13]?Вам придется написать код, который найдет все общие знаменатели, и его будет не так легко прочитать.

Answer 6

Однострочник:

(3...1000).find_all {|n| n % 3 == 0 || n % 5 == 0}.inject(:+)

Ruby такой элегантный!

Answer 7

public class Sample {

  public static void main(final String args[]) {

    // Find the sum of all the multiples of 3 or 5 below 1000.
    int temp = 0;

    for (int i = 1; i <= 1000; i++) {

        if ((i % 3 == 0) && (i % 5 == 0)) {
            System.out.println(i);
            // add them
            temp = temp + i;
        }
    }
    System.out.println(temp);
   }
}

Answer 8

(1..999).select { |num| (num % 3 == 0) || (num % 5 == 0) }.reduce(:+)

Здесь мы #select из диапазона всех num с, которые делятся на 3 или 5. В результате получается Array.

Затем мы можем соединить #reduce и :+ для суммирования всех элементов в массиве.

Answer 9

Простая формула может быть числа, кратные 3 + число, кратное 5 - число, кратное 3 и 5 нет = 10

итого total_no = 3 + 2-0 = 5 (3,5,6,9,10)

total_no = (нет / 3) + (нет / 5) - (нет / 15)

Answer 10

в одну строку

(0..1000).to_a.reject!{|a| (a%3 != 0 && a%5 != 0) }.inject(0) { |s,v| s += v }

Как указано ниже, следующее неверно

(0...1000).to_a.reject!{|a| (a%3 == 0 || a%5 == 0) }.inject(0) { |s,v| s += v }