斐波那契数列：寻找复合问题

Question

我想找到一对 GCD（最大公分母）为 1 的数字，序列 X0、X1、... XN 的前 N 项都是合数。

对于我的代码，出于某种原因，它在 i == 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

问题是您的 is_prime 函数速度变慢，而不是在您的 for 循环中检查每个数字是否为质数。为什么不生成一个素数列表，比如说前 100 万个，将它们存储在一个列表中。然后还要检查你的号码是否为素数，只需检查它是否在列表内。

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。

The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

有关它的更多信息，请访问 Wikipedia。

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.")

这是完整的代码，正如您在运行时看到的 returns 结果

143 142
>>>

Answer 2

正如我在评论中提到的，您需要一个更好的素数测试算法，这些算法可能很难理解或自己实现，因此您可以使用提供它的库，例如 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

斐波那契数列：寻找复合问题

Fibonacci Sequence: Finding Composites Problem

python

fibonacci