Project Euler 1: Find the sum of all multiples of 3 or 5 below 1000

Question

I am trying to solve math problems with Ruby from Project Euler. Here is the first one I tried:

If we list all natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all multiples of 3 or 5 below 1000.

Please help me improve my code.

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

Answer 1

The answer is much faster (constant time):

 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 

Why does it work? sum_multiples sum of the multiples of multiple up, but not including to (it relies on integer division). First, it calculates the number of summed sums ( n ), then multiplies the standard formula by the sum 1..n = n (n + 1) / 2 by multiple . Using this, we can sum the sums for multiples of 3 and 5. Then we should not forget that some numbers are multiples of both 3 and 5, so we subtract the multiples of 15 (3 * 5).

Although your answer is more than fast enough for limitations in this problem (it should work for about 1 millisecond on modern equipment), a faster solution, such as the one I provide, will produce results in very large quantities.

Answer 2

here is my approach that I will find (1, 333) for 3 * k (3,6,9 ...) and (1200) for 5 * k.

• Count all divisible by 3 and calculate the sum
• Count all divisible by 5 and calculate the sum
• A number divisible by 15 must be considered one

3 * (1 + 2 + 3 + ... + 333) + 5 * (1 + 2 + 3 ..) - 15 * (1 + 2 ...), which you can formulate with n * (n + 1) / 2 , and this is O (1) , but I am implementing my code with a loop

and here is my first Ruby code :)

 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 

here is a demo

Answer 3

Well, at first you can skip about 666 numbers, starting from 3, increasing by 3. Thus, you only consider multiples of 3. So then do the second cycle, starting from 5, increasing by 5. Here you need to check the number of multiples of 3 (or skip every third generated number, as it so happens that they will be a multiple of 3), since they were summed before.

This will allow you to check ~ 500 numbers, approximately half of the required numbers.

Alternatively, you can see if you can find a closed form for the sum (in principle, sum the numbers from 1 to gender (max, N), multiply this by N, do this for your Ns (3 and 5), but then you you have to subtract double-counted numbers, but this essentially subtracts the same thing for N = 15).

Answer 4

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

Answer 5

Another way to do this exactly as stated in the problem:

 ((1..(999/3)).map {|x| x*3} | (1..(999/5)).map {|x| x*5}).reduce(&:+) 

But the constant answer of marcog is the better way.

Answer 6

In one line

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

As indicated below, the following was not true:

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

Answer 7

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

Here we are #select ing from the range of all num , which are divided by 3 or 5. The result is an Array .

Then we can chain on #reduce and :+ to sum all the elements in the array.

Answer 8

 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 9

A simple formula can be nos that are a multiple of 3 + a number, a multiple of 5 - a number, a multiple of 3 and 5 no = 10

so total_no = 3 + 2-0 = 5 (3,5,6,9,10)

total_no = (none / 3) + (none / 5) - (none / 15)