三角形の数にはどのような要因がありますか？

Question

私はProject Euler Problem 12を行っていましたが、問題が発生しました。私のコードは以下の通りです：

def print_factors(x): 
    count = 0 
    for i in range(1, x + 1): 
     if x % i == 0: 
      count = count + 1 
    return count 
count = 0 
div = 0 
while True: 
    if print_factors(count + count + 1) == 500: 
     print(count) 
     break; 
    count = count + 1 

もっと速い方法がありますか？これは長すぎます。

Answer 1

すべての三角形の数に対して、2から始まる素数を反復することができます。素数ごとに、何回に分割できるかをチェックします。例えば、28は、28/2 = 14と14/2 = 7なので、2で2回に分割できます。次に、現在の除数の数にtimes + 1を掛けます。次に、leftoverをnumberに割り当て、次のプライムに移動します。 while prime <= numberを繰り返します。以下は実際にそれを実装するコードです：

# Generate bunch of primes and cache them for efficiency 
primes = [2, 3] 

for i in xrange(5, 1000): 
    for j in primes: 
     if i % j == 0: 
      break 
    else: 
     primes.append(i) 

i = 2 
while True: 
    res = triangle = i * (i - 1)/2 
    divisors = 1 

    for j in primes: 
     if j > triangle: 
      break 

     cur = 1 
     while triangle % j == 0: 
      triangle /= j 
      cur += 1 

     divisors *= cur 

    if divisors > 500: 
     break 
    i += 1 

print res 

Answer 2

これは私のコードです。

!/usr/bin/python 
primes = [2] 
def fp(): 
    i=3 
    while i<10000: 
     for j in primes: 
      if i%j == 0: 
       break 
     else: 
      primes.append(i) 
     i+=1 
def fac(n): 
    f={} 
    i = 0 
    while n > 1: 
     p=primes[i] 
     if p*p > n : 
      p=n 
     while n%p==0: 
      f[p]=f.get(p,0)+1 
      n/=p 
     i+=1 
    n=1 
    for i in f: 
     n*=f[i]+1 
    return n 

from time import time 
def f1(): 
    t=time() 
    fp() 
    j=0 
    i=0 
    max = 0 
    while True: 
     i+=1 
     j+=i 
     f=fac(j) 
     if f >= 500: 
      break 

    print j,f 
    print time()-t 

f1() 

EDITED：

素数：（FPによって構築された）最後の素数少ないより10000

FP 2〜素数を含むリストは、：10000より小さいすべての素数を見つけますそれらを「素数」に格納します。この後に素数を何度もチェックしなければならないので、事前に見つけてリストに格納することで全体の処理が速くなります。この関数は高速です。1.素数2だけを通過します。これは、ターゲット番号のsqrtで停止します。

fac：与えられた数のファクタの数を資金提供するファンクション。ブルートフォースよりも優れているのは、「素数」リストを使用してすべての素因数を見つけようとしているからです。目標数のsqrtで停止します。すべての素数を知った後、異なる素数の数の乗算である何らかの組合せアルゴリズムを使用して、因子の数を計算します。

例：40 =（2 * 2 * 2）（5）次いで、40（3（+1））（1（+1））= 8因子

説明している：あなたが考えることができ2つのマテリアルグループ（この例では2と5）があり、これらのマテリアルを混合することによって得られる結果の数を見つけたいという問題があります。マテリアル '2'に焦点を当てれば、2を得るためには '2'を1つだけ選択し、4を得るには2を、2を得るには2を選択することができます。 3回発生する素因数から+1の可能性。 '5'と同じですが、あなたはそれを選択したり選択を解除することで1 +1の可能性があります。それは（+1）が来る方法です。

f1：主な機能。次の三角形の数にジャンプし、500以上の要素を持つものを見つけて停止し、時間を印刷します。

Answer 3

この非常に良い解決策はhttp://www.tech-thoughts-blog.com/2012/08/1-introduction-in-this-article-i-will.htmlに完全に基づいています。ここではrahmuがコードと優れた説明を提供しています。それが元のコードより速いのか、それとも他のソリューションが提供されるのかに関わらず、私は確信していません。私のマシンでは、約6秒で答えを出します。

from collections import Counter 
from operator import mul 
from functools import reduce 


def prime_factors(n): 
    """ 
    Generates all the prime factors of a positive integer n 
    :param n: 
    """ 
    d = 2 
    while n > 1: 
     while n % d == 0: 
      n /= d 
      yield d 
     d += 1 


def format_prime(n): 
    """ 
    Returns a collection.Counter() built from the prime factors decomposition of n. 
    :param n: 
    """ 
    return Counter(prime_factors(n)) 


def prime_count(c): 
    """ c is a Counter() object holding the prime factor decomposition of an integer. It returns the total number of 
    divisors by applying the following formula: 
    Let N = a^x * b^y * c^z (a, b and c prime) and F(N) the total number of divisors of N. 
    F(N) = (x + 1) * (y + 1) * (c + 1) 
    :param c: 
    """ 
    return reduce(mul, (c[j] + 1 for j in c)) 


def triangle(k): 
    """ 
    k is an int. This function returns a collections.Counter that is the application of triangle(k) = k * (k+1)/2. 
    :param k: 
    """ 
    a = format_prime(k) 
    b = format_prime(k+1) 
    c = a + b 
    c[2] -= 1 # This is equivalent to a division by 2 
    return c 

if __name__ == "__main__": 
    i = 2 
    number_of_factors = 500 
    while prime_count(triangle(i)) <= number_of_factors: 
     i += 1 
    print(i * (i+1) // 2)