Fibonacci序列:寻找复合材料问题

Question

我正在寻找一对GCD (最大公分母)为1的数字，这是序列X0，X1，……的第一个N项。XN都是合成的。

对于我的代码，由于某种原因，当我== 15、j == 878和k == 78时，它会被卡住。当在列表中的最后两个项上运行is_prime()时，它会陷入困境。

import math


def is_prime(num):
    if num < 2:
        return False
    for x in range(2, math.floor(math.sqrt(num)) + 1):
        if num % x == 0:
            return False
    return True


# create list containing a range of composite numbers
numbers = []
for i in range(4, 200):
    if not is_prime(i):
        numbers.append(i)

for i in numbers:
    found = False
    for j in numbers:
        if math.gcd(i, j) == 1:
            # print(i, "-", j, end=" | ")
            fibonacci = [i, j]
            contains_prime = False
            for k in range(2, 500):
                if is_prime(fibonacci[-2] + fibonacci[-1]):
                    contains_prime = True
                    break
                else:
                    fibonacci = [fibonacci[-1], fibonacci[-2] + fibonacci[-1]]
            if not contains_prime:
                print(i, j)
                found = True
        if found:
            break
    if found:
        break
    if i == numbers[-1]:
        print("No Possibilities Exist.")

Answer 1

正如我在评论中提到的，您需要一个更好的原始性测试算法，这些算法很难单独理解或实现，因此您可以使用一个库来提供它，例如，可以像sympy那样使用pip来安装它，并将其用作：

import math
from sympy.ntheory import isprime 

# create list containing a range of composite numbers
numbers = []
for i in range(4, 200):
    if not isprime(i):
        numbers.append(i)

for i in numbers:
    found = False
    for j in numbers:
        if math.gcd(i, j) == 1:
            fibonacci = [i, j]
            contains_prime = False
            for k in range(2, 500):
                if isprime(fibonacci[-2] + fibonacci[-1]):
                    contains_prime = True
                    break
                else:
                    fibonacci = [fibonacci[-1], fibonacci[-2] + fibonacci[-1]]
            if not contains_prime:
                print(i, j)
                found = True
        if found:
            break
    if found:
        break
    if i == numbers[-1]:
        print("No Possibilities Exist.")

现在是快速运行，没有卡住和打印的结果：143 142

Answer 2

问题是您的is_prime函数是慢的，而不是检查每个数字是否是for循环中的素数。为什么不生成一个素数列表，比如说前一百万，把它们存储在一个列表中。然后也检查你的数字是否是素数，只需检查它是否在列表中。

import math

def gen_prime(n):
    D = {}
    q = 2

    for i in range(n):
        if q not in D:
            yield q
            D[q * q] = [q]

        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

primes = [i for i in gen_prime(1_000_000)]

def is_prime(num):
    if num in primes:
        return True
    else:
        return False

# create list containing a range of composite numbers
numbers = []
for i in range(4, 200):
    if not is_prime(i):
        numbers.append(i)

for i in numbers:
    found = False
    for j in numbers:
        if math.gcd(i, j) == 1:
            # print(i, "-", j, end=" | ")
            fibonacci = [i, j]
            contains_prime = False
            for k in range(2, 500):
                if is_prime(fibonacci[-2] + fibonacci[-1]):
                    contains_prime = True
                    break
                else:
                    fibonacci = [fibonacci[-1], fibonacci[-2] + fibonacci[-1]]
            if not contains_prime:
                print(i, j)
                found = True
        if found:
            break
    if found:
        break
    if i == numbers[-1]:
        print("No Possibilities Exist.")

当运行这段代码时，我会得到结果

18 187
>>> 

编辑:我决定对素数算法做一些研究，我偶然遇到了米勒-拉宾。

Miller-Rabin素数检验或Rabin-Miller素数检验是一种概率素数检验:与Fermat素数检验和Solovay-Strassen素数检验相似的确定给定数是否为素数的算法。

有关它的更多信息可以在维基百科上找到。

import random, math

# miller_rabin algorithm
def is_prime(n, k = 40):
    if n == 2:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2

    for i in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue

        for i in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break

        else:
            return False

    return True

# create list containing a range of composite numbers
numbers = []
for i in range(4, 200):
    if not is_prime(i):
        numbers.append(i)

for i in numbers:
    found = False
    for j in numbers:
        if math.gcd(i, j) == 1:
            # print(i, "-", j, end=" | ")
            fibonacci = [i, j]
            contains_prime = False
            for k in range(2, 500):
                if is_prime(fibonacci[-2] + fibonacci[-1]):
                    contains_prime = True
                    break
                else:
                    fibonacci = [fibonacci[-1], fibonacci[-2] + fibonacci[-1]]
            if not contains_prime:
                print(i, j)
                found = True
        if found:
            break
    if found:
        break
    if i == numbers[-1]:
        print("No Possibilities Exist.")

下面是完整的代码，在运行时可以看到，它返回结果

143 142
>>>