0

通常、次のコードを使用して、特定の n (タウ関数) までの除数の数を見つけます。

L=[0 for i in range(N+1)]
for i in range(1,N+1):
    for j in range(i, N+1,i):
        L[j]+=1
print L

どの出力

[0, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4]

しかし、代わりに n^2 の約数を出力したい場合はどうすればよいでしょうか? 今は n=0,1,2,3,4,5,6,7,8,9,10 を見ていますが、実際には 0,1,4,9,16 を見ているように変更したいのですが、 25、36、49、64、81、100 (他の数字をいじる必要はありません)。

出力は次のようになります。

[0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9]
4

3 に答える 3

2

大きさによってnは、Nolen の回答で十分な場合があります (公平を期すために、元のコードは最初から最適化されていません)。n**2 ただし、 が何であるかは注目に値します。数を因数分解できる場合、たとえば10、次のようになります。

10    = (2**1)*(5**1)
10**2 = (2**(1+1))*(5**(1+1)) = (2**2)*(5**2)

つまり、素因数分解の指数の数は単純に 2 倍になります。数値の素因数分解n(コードを変更することができます) を既に見つけることができると仮定すると、除数の数はn**2(疑似コード) によって見つけることができます。

div  := (list of divisors of n)
div2 := (a list with two copies of div)
loop through all combinations div2:
      if combo <= sqrt(n): keep unique

これを行うと、次の10ようになります。

div  := (1,2,5,10)
div2 := (1,2,5,10,1,2,5,10)
keep := (1,2,5,10,2*2,2*5) 
unique_keep := (1,2,4,5,10)

unique_keepしたがって、分割された各数値に10**2=100は、それ自体の因数である 10 の特異なケースを除いて、対応する因数もあります。これにより、除数が 9 になります。

1 -> 100
2 -> 50
4 -> 25
5 -> 20
10 -> 10
于 2012-04-16T14:29:46.020 に答える
0

こんなもの欲しいと思いますか？

>>> [sum(i**2 % j == 0 for j in range(1, i**2 + 1)) for i in range(11)]
[0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9]

またはより一般的に

>>> def divisors(start, end, trans=lambda x:x):
...     return [sum(i % j == 0 for j in range(1, i + 1)) for i in (trans(t) for t in range(start, end+1))]
... 
>>> divisors(0, 10, lambda x: x**2)
[0, 1, 3, 3, 5, 3, 9, 3, 7, 5, 9]
>>> divisors(0, 10)
[0, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4]
于 2012-04-16T14:01:07.623 に答える
0

数の素因数がある場合、素因数の数を計算するのは、その 2 乗の因数 (または実際には任意の累乗) を計算するのと同じくらい簡単です。

def factor_count(N,power):
    factor_count = list()
    for n in range(N+1):
        prime = 2
        prime_factors = list()
        exponents = list()
        while n > 1:
            while (n / prime) % 1 == 0:
                if prime not in prime_factors:
                    prime_factors.append(prime)
                    exponents.append(1)
                else:
                    exponent = exponents.pop()+1
                    exponents.append(exponent)
                n /= prime
            prime += 1
        factors = 1
        for x in exponents:
            factors *= power*x+1
        factor_count.append(factors)
    print(factor_count)

また、私のプログラムは、ゼロの因数の数に関して、あなたのプログラムとは異なることに注意してください。これを考慮してコードを変更するのは簡単ですが、除数は自然数に対して定義されることが多いため、それを完全に無視するのも同じくらい簡単です。

与えられた他の回答と比較して、これがどれほど効率的であるかを理解するには：

power_factors(1000,2000000000)                                        #evaluates almost instantly despite having an exponent of 2 billion
[sum(i**2 % j == 0 for j in range(1, i**2 + 1)) for i in range(1001)] #I got fed up of waiting before it managed to finish even with just an exponent of 2
于 2012-04-16T17:00:50.967 に答える