セットAの関係Rを表す行列の0でないエントリを、Pythonコード

Question

でカウントしました。以下の問題を解決するコードを作成しました。それは動作しますが、効率的ではありません。誰かがそれをもっとPythonicにするための推奨を持っていますか？

最初の100個の正の整数からなる集合の関係を表す行列は、ifが{（、）| 1を除いて共通の除数を持つ}？

def commonDivisor(n): 
    nums = list(range(2, n+1)) 
    sum = 0 
    for idx, num in enumerate(nums): 
     if num % 2 == 0 and num % 3 != 0 and num % 5 != 0: 
      sum += 50 
      print(idx,num,sum) 

     elif num % 2 != 0 and num % 3 == 0 and num % 5 != 0: 
      sum += 33 
      print(idx,num,sum) 

     elif num % 2 != 0 and num % 3 != 0 and num % 5 == 0: 
      sum += 20 
      print(idx,num,sum) 

     elif num % 2 == 0 and num % 3 == 0 and num % 5 != 0: 
      sum += (50 + 33 - (100//(2*3))) 
      print(idx,num,sum) 

     elif num % 2 == 0 and num % 3 != 0 and num % 5 == 0: 
      sum += (50 + 20 - (100//(2*5))) 
      print(idx,num,sum) 

     elif num % 2 != 0 and num % 3 == 0 and num % 5 == 0: 
      sum += (33 + 20 - (100//(3*5))) 
      print(idx,num,sum) 

     elif num % 2 == 0 and num % 3 == 0 and num % 5 == 0: 
      sum += (50 + 33 + 20 - (100//(2*3*5))) 
      print(idx,num,sum) 

     else: 
      sum += (100//num) 
      print(idx,num,sum) 

    return sum 

Answer 1

数100は大きくなく、サイズ100のあなたの関係行列のエントリ数は、コンピュータプログラムの大きさではありません100**2 = 10000です。 math.gcdは、2つの数値が共通の除数が1より大きく、math.gcd(a, b)を計算する時間の複雑さがO(log(min(a,b)))であるかどうかを検出します。 GCDをチェックして100までの数字のすべてのペアを調べると、これは唯一46052の複雑さになりますが、これもやはり大きくありません。

だから、あなたがこのニシキヘビコードで直接的な方法あなたの数を計算することができます

from math import gcd 
n = 100 
print(sum(1 for a in range(1, n+1) for b in range(1, n+1) if gcd(a,b) > 1)) 

これは、簡単なニシキヘビで、ゼロ以上nの任意の値で動作します。

3913のコードは3756を返します。私のコードは非常に単純なようで、nの小さな値をチェックするので、コードが間違っていると思われます。あなたのコードはn=100に非常に限定されているため、チェックすることは非常に困難です。しかし、あなたは2,3,5以外のすべての素因数を無視するようです。 (7, 49)、(11, 22)、(97, 97)などの可能性を除外します。

nという大きな値の場合、私のコードは遅くなります。以下は、同じことを計算するが、大規模の場合にははるかに高速であるはるかに複雑なコードですn。 n=100の場合、私の古いコードは2.7ミリ秒を使用しますが、私の新しいコードは139 マイクロ秒の約1/20です。この差異は、より大きなnの方が大きいでしょう。

このコードは、100未満の素数の組み合わせを見つけます。2つの数字は、少なくとも1つの素数で割り切れる場合（両方の数字が同じ素数）、2より大きい共通の除数を持ちます。たとえば、100 // 2の数字は1から100まで2で割り切れるので、(100 // 2) ** 2の数字のペアは、それ自体が2で割り切れる共通の係数を持ちます。(100 // 3) ** 2の数字のペアは、それ自体が3で割り切れる共通の係数を持ちますが、等々。これらのカウントは重複するため、Inclusion–exclusion principleを使用して繰り返しカウントを削除する必要があります。我々はを差し引くによって割り切れる数は 2と3はその重なりを取り除く。マイコード内の乗算器1 if len(c[0]) % 2 else -1が加算/減算の決定を処理します。

新しいコードでは、素数のリストも使用します。私の意見では、分裂性の仕事をしている人は、計算を大幅に高速化するために利用可能な素数の長いリストを持つべきです。私自身のリストには最初の6542個の素数があり、すべて2バイトの符号なし整数に収まるものです。

primeslist = [ 
     2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
] 

def prime_combinations(n): 
    """Generate combinations of distinct primes where their product is 
    less than n. Each yielded item is a 3-tuple containing: 
    - the combination in increasing order, 
    - the product of the primes in the combination, 
    - k where the last and largest prime in the combination is the k'th 
     prime (where 2 is the 1st prime.) 
    Items are yielded in lexicographical order. The first item yielded 
    is the empty combination ((), 1, 0). 
    """ 
    def primecombos(prefix, prod, ndx): 
     yield prefix, prod, ndx 
     while True: 
      newprime = primeslist[ndx] 
      newprod = prod * newprime 
      if newprod >= n: 
       return 
      yield from primecombos(prefix + (newprime,), newprod, ndx+1) 
      ndx += 1 

    if 1 < n <= primeslist[-1] and n == int(n): 
     yield from primecombos((), 1, 0)  

def commonDivisor2(n): 
    """Count the number of pairs of positive integers less than or 
    equal to n that have a common factor greater than 1. 
    """ 
    pcombs = prime_combinations(n+1) 
    next(pcombs) # throw away the empty combination of primes 
    return sum((1 if len(c[0]) % 2 else -1) * (n // c[1]) ** 2 
       for c in pcombs) # c[0] is combination, c[1] its product