2

正の整数の 2 つのリストが与えられたとき、それらの合計が素数になるように各リストから数値を選択できる方法は何通りあるかを求めます。

list1 と list 2 の両方にそれぞれ 50000 個の数字が含まれているため、コードが遅すぎます。それで、それをより速くして、数日ではなく数分で解決する方法はありますか?? :)

    # 2 is the only even prime number
    if n == 2: return True

    # all other even numbers are not primes
    if not n & 1: return False

    # range starts with 3 and only needs to go 
    # up the squareroot of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0: return False

    return True



for i2 in l2:
    for i1 in l1:
        if isprime(i1 + i2):
            n = n + 1 # increasing number of ways
            s = "{0:02d}: {1:d}".format(n, i1 + i2)
            print(s) # printing out
4

3 に答える 3

1

素数を計算するには、エラトステネスのふるいを使用する必要があります。

また、合計の可能な組み合わせごとに素数を計算しています。代わりに、リストの合計で達成できる最大値を見つけることを検討してください。その最大値までのすべての素数のリストを生成します。

数字を合計している間に、その数字が素数リストに表示されるかどうかを確認できます。

于 2013-10-12T21:42:08.723 に答える