The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Let us list the factors of the first seven triangle numbers:
hosiawak, Twój warunek nie jest poprawny. Użyj find zamiast take_while i zmień warunek na num_divisors(x) > 500.
Moje rozwiązanie opiera się na prawie, że po rozłożeniu liczby x na czynniki pierwsze i zapisie tej liczby w postaci:
x = p1^e1 + p2^e2 + … + pn^en
gdzie p1, p2… pn to czynniki pierwsze, zaś e1…en to ilość wystąpień czynnika w rozkładzie pierwszym liczby
to liczba dzielników liczby wynosi
(e1 + 1) * (e2 + 1) * … * (en + 1)
[code=ruby]def divisors(n)
d = []
2.upto(Math.sqrt(n).floor) do |i|
p = 0
while n % i == 0
p += 1
n /= i
end
if p > 0
d << p
end
end
return d.empty? ? 2 : (d.inject(1) {|acc, pow| acc * (pow + 1) } )
end
def triangle
a, b = 1, 1
loop do
yield a
b += 1
a += b
end
end
hosiawak, Twój warunek nie jest poprawny. Użyj find zamiast take_while i zmień warunek na num_divisors(x) > 500.
Moje rozwiązanie opiera się na prawie, że po rozłożeniu liczby x na czynniki pierwsze i zapisie tej liczby w postaci:
x = p1^e1 + p2^e2 + … + pn^en
gdzie p1, p2… pn to czynniki pierwsze, zaś e1…en to ilość wystąpień czynnika w rozkładzie pierwszym liczby
to liczba dzielników liczby wynosi
(e1 + 1) * (e2 + 1) * … * (en + 1)[/quote]
radarek znowu pozamiatał
Chyba mi się udało zejść poniżej minuty . Sprawdź sam hosiawak czy mój skrypt na twoim sprzęcie zejdzie poniżej minuty.
[code=ruby]#!/usr/bin/env ruby
N = 500
def divisions2(x)
x /= 2 if x%2 == 0
(1…Math.sqrt(x).floor).inject([]) do |t, d|
t += (x%d == 0 ? (x/d == d ? [d] : [d, x/d]) : [])
end
end
i = 1
td1 = divisions2(1)
while true
x = (i*(i+1))/2
td2 = divisions2(i+1)
hd = { }
y = td1.inject(0) do |s1, d1|
s1+td2.inject(0) do |s2, d2| i
unless hd[d1d2]
hd[d1d2] = true
s2+1
else
s2
end
end
end
break if y > N
td1 = td2
i += 1;
end
Korzystając z rozwiązania radarka i STDLIB ruby1.9:
require 'prime'
def triangle
a, b = 1, 1
loop do
yield a
b += 1
a += b
end
end
p enum_for(:triangle).find {|x| x.prime_division.collect(&:last).inject(1) {|product, e| product * (e + 1)} > 500 }
Wyniki na moim e8200:
real 0m1.490s
user 0m1.488s
sys 0m0.000s
A i kod ładniejszy i krótszy
Heh chciałbym. Ale mój procesor to jak napisałem e8200 - 2 rdzenie po 2,66 GHz. Później jak będe miał do niego dostęp to sprawdze jak szybkie jest twoje rozwiązanie.
