2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
Naiwny algorytm, ale po 3 min znalazł :P. Wersja wymaga działa na >= 1.8.7 (inject z symbolem metody).
puts 1.upto((2..20).inject(:*)).each {|n| break n if (2..20).all? {|e| n % e == 0} }[code=ruby]P = [2,3,5,7,11,13,17,19]
d = []
(1…20).each do |n|
p,x = 0, []
while n > 1
if n % P[p] == 0
n /= P[p]
x[p] ||= 0
x[p] += 1
else
p+=1
end
end
x.each_with_index do |e,i|
if e
d[i] ||= 0
d[i] = [d[i], e].max
end
end
end
s = 1
d.each_with_index do |e, i|
s *= P[i] ** e
end
puts s
(1…20).each do |e|
puts 232792560 % e
end[/code]
Konkurs: kto wie o co tu chodzi :>
(zeby nie bylo - ja wiem :P)
[quote=radarek]puts 1.upto((2..20).inject(:*)).each {|n| break n if (2..20).all? {|e| n % e == 0} }
[/quote]
Dolne ograniczenie to iloczyn liczb pierwszych, a podzielność przez 11…20 gwarantuje podzielność przez 1…10; odrobinę szybciej też eliminuje się kandydatów sprawdzając podzielność od największego dzielnika. Tak czy siak, poniższe rozwiązanie nadal jest tylko kilkanaście procent szybsze od powyższego:
require 'prime'
divisors = (11..20).to_a.reverse
lower = (1..20).select(&:prime?).inject(:*)
upper = divisors.inject(:*)
(lower..upper).find { |n| divisors.all? { |div| n % div == 0 } } # => 232792560
Ale skoro rozwiązanie musi być podzielne przez iloczyn liczb pierwszych, to wystarczy sprawdzać wielokrotności tego iloczynu (i tylko podzielność tych wielokrotności przez nie-pierwsze z 11…20) – a to już jest dużo szybsze:
require 'prime'
divisors = (11..20).reject(&:prime?).reverse
lower = prime_factor = (1..20).select(&:prime?).inject(:*)
lower += prime_factor until divisors.all? { |div| lower % div == 0 }
lower # => 232792560
Tak na oko – o coś w rodzaju odwrotnej faktoryzacji? 
Tak przy okazji, nie wiem czy wszyscy o tym wiedzą, ale:
lower += prime_factor until conditionto nie to samo co
until condition
lower += prime_factor until
end
W tym 1 przypadku najpierw wykona się ciało metody, a potem sprawdzany jest warunek, w tym 2 jest odwrotnie. Zatem w 1 przypadku ciało pętli wykona się przynajmniej raz.
W tym zadaniu akurat to nie ma znaczenia, ale warto znać różnicę.
[quote=radarek]Tak przy okazji, nie wiem czy wszyscy o tym wiedzą, ale:
lower += prime_factor until conditionto nie to samo co
until condition
lower += prime_factor until
end
W tym 1 przypadku najpierw wykona się ciało metody, a potem sprawdzany jest warunek, w tym 2 jest odwrotnie. Zatem w 1 przypadku ciało pętli wykona się przynajmniej raz.[/quote]
E tam.
[code]shot@devielle:~$ ruby -v; irb --simple-prompt
ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
a = 1
=> 1a += 1 until true
=> nila
=> 1[/code]
[code]shot@devielle:~$ ruby -v; irb --simple-prompt
ruby 1.9.1p0 (2009-01-30 revision 21907) [i686-linux]
a = 1
=> 1a += 1 until true
=> nila
=> 1[/code]
Ach, poprawka. Wiedziałem, że coś mi świta. Chodzi o coś podobnego:
[code=ruby]begin
puts “!”
end while false
vs
puts “!” while false[/code]
[quote=radarek]Ach, poprawka. Wiedziałem, że coś mi świta. Chodzi o coś podobnego:
[code=ruby]begin
puts “!”
end while false
vs
puts “!” while false[/code]
[/quote]
No tak, ale to jest już standardowa różnica, znana też z innych języków: while (cond) {…} działa inaczej niż do {…} while (cond)
Zauważ też, że
[1,2,3].each { |e| p e } while falsenic nie wypisuje, więc to kwestia użycia begin…end, a nie miejsca umieszczenia while.
Ruby 1.9
(1..20).inject(:lcm)
to mnie rozwala 
Jeśli chodzi o temat to powinno być “Problem 5” a nie “Probelm 5”
Już poprawiłeś co
d = 0
dividable = false
while !dividable
d += 1
if (1..20).select {|x| d % x == 0 }.length == 20
dividable = true
end
end
puts d
działa… dlugo działa