2017-10-09 6 views
-6

私はEuler Project No 12を解決するためにこのコードを書いていますが、コードが遅くなります。このコードをもっと速くするにはどうすればよいですか?

どうすれば速く動作させることができますか?私は除数を見つけることについていくつかの示唆を読んだが、nsqrtを使用するという論理を理解していない。

あなたはその論理を説明できますか? n

def sumdiv(n): 
    l=[d for d in range(1,int(n/2)+1) if n%d==0] # used n/2 to short loop 
    return len(l)+1 # added n itself 
trnums=[1,3] 

while sumdiv(trnums[-1])<=501: 
    k=trnums[-1]-trnums[-2]+1 
    trnums.append(trnums[-1]+k) 
print(trnums[-2:]) 
+1

使用 '範囲のDのための[D (1、int(math.sqrt(n))+ 1)if n%d == 0] 'の場合、この点の後には除数は見つかりません。それはあなたのコードをより速くします。 –

+0

私はすでにこの方法を知っていますが、sqrtを使用するロジックが必要です –

+2

質問は「int(math.sqrt(n))+ 1」で停止する必要がありますか? – Adirio

答えて

0

abある除数a * b = n場合:

は、ここに私のコードです。一般性を失うことなく、b >= aを設定することができます。したがって、a * aが上限です。すなわち、nの平方根までを考慮する必要があります。 aを取得すると、簡単にbを推測できます。

あなたはその平方根の任意の計算を不要にするd * d <= nのではなくd <= sqrt(n)ように上限を設定することができます。まだまだ速いでしょう。

+0

lest take fまたは例28. –

+0

28の約数は1,2,4,7,14,28です。私は自分のコードを変更しました。しかし、asnwerが間違っている –

+0

n = 28 (i、int(n ** 0.5)+1): n%i == 0の場合: print(i) –

0

あなただけの約数の数を知りたい:すべてのdividor xがある場合を除き、Nの除数自身であること、他のyを掛けたことを必要とする約数の偶数が常に存在している任意の数のNについて

x=sqrt(N)は、結果として整数結果をx*x=Nと意味し、それは唯一の数値になります。したがって、すべての除数は、除数になる場合はsqrt(N)を除いてペアにグループ化されます。

ルートは除数で、その後、それまで計算し、残りは常にペアになるように、それぞれの時間をカウントに2を追加する場合、あなた最初のチェック:

def number_of_divisors(n): 
    root = math.sqrt(n) 
    if root == int(root): 
     number = 1 
     limit = int(root) 
    else: 
     number = 0 
     limit = int(root) + 1 
    for i in range(1, limit): 
     if (n % i) == 0: 
      number += 2 
    return number 

i = 1 
s = 1 
while number_of_divisors(s) < 501: 
    i += 1 
    s += i 

print(i) # 12375 
print(s) # 76576500 
print(number_of_divisors(s)) # 576 
関連する問題