5

Python で 65 個を超える素数を含む最小のコラッツ シーケンスを見つける必要があるタスクがあります。

たとえば、19 のコラッツ数列は次のとおりです。

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

この数列には 7 つの素数が含まれています。

それを見つけるために「年」を実行する必要がないように、メモ化も使用する必要があります。Collat​​z シーケンスのメモ化のコードを見つけましたが、素数だけが必要な場合にそれを機能させる方法がわかりません。

私が見つけたCollat​​zのメモ化コードは次のとおりです。

lookup = {}
def countTerms(n):
    if n not in lookup:
        if n == 1:
            lookup[n] = 1
        elif not n % 2:
            lookup[n] = countTerms(n / 2)[0] + 1
        else:
            lookup[n] = countTerms(n*3 + 1)[0] + 1

    return lookup[n], n

そして、ここにプライムのテスターがあります：

def is_prime(a):
    for i in xrange(2,a):
        if a%i==0:
            #print a, " is not a prime number"
            return False
    if a==1:
        return False
    else:
        return True
4

2 に答える 2