Created
July 8, 2011 04:50
-
-
Save tarsisazevedo/1071172 to your computer and use it in GitHub Desktop.
euler 12
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from unittest import TestCase, main | |
| import math | |
| class TestNumerosTriangulares(TestCase): | |
| def test_numero_28_deve_ter_5_divisores(self): | |
| """docstring for test_numero_28_deve_ter_5_divisores""" | |
| self.assertEquals(primeiro_numero_triangular_com(divisores=5), 28) | |
| def test_numero_x_deve_ter_500_divisores(self): | |
| """docstring for test_numero_x_deve_ter_500_divisores""" | |
| self.assertEquals(primeiro_numero_triangular_com(divisores=500), 76576500) | |
| def primeiro_numero_triangular_com(divisores): | |
| divisores_numero = 0 | |
| posicao_na_sequencia = 1 | |
| while divisores_numero <= divisores: | |
| posicao_na_sequencia += 1 | |
| proximo_numero = sum(range(1, posicao_na_sequencia + 1)) | |
| numero = int(math.sqrt(proximo_numero)) | |
| divisores_numero = len([i for i in range(1, numero + 1 ) if proximo_numero % i == 0]) * 2 | |
| return proximo_numero | |
| main() |
Eu fiz de forma diferente. Sei que existe uma propriedade que diz que
dado que x possa ser fatorado (em fatores primos) como x1^k1 + ... + xm^km
o número x tem exatamente
(k1 + 1) * ... * (km + 1) divisores próprios
Com isso, tenho essa solução: https://github.com/juanplopes/euler/blob/master/0012.boo
Que sai em 0.4s (mas é compilado)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
O @cabello me ajudou nessa solucao, no canal do #cobrateam no irc. Obrigado cara!
ele demonstrou uma propriedade muito interessante:
O numero 28 tem 6 divisores. Se voce tirar a raiz quadrada dele, terá ~5.3, levando em conta só os numeros naturais, teremos 5.
de 1 a 5, o numero 28 tem 3 divisores, 1, 2, 4. Calculando, temos: 1_28, 2_14 e 4*7. Se olharmos com calma, deduzimos que os divisores andam em pares!
Dada esta propriedade, eu posso usar a raiz do numero 76576500, calcular somente seus primeiros 250 divisores e consigo validar que ele é o primeiro numero triangular que tem mais de 500 divisores muito mais rapido! (11 seg)
falei merda @cabello?!
Obrigado mais uma vez cara!