低效的算法！你能帮我提高效率吗？

Question

在数学中，丢番图方程是一个多项式方程，通常有两个或两个以上的未知数，因此只寻求或研究整数解

这是一个方程式： x**2 - 4 * y**2 = n

（其中未知数是x和y，并且n是给定的正数

我的函数遍历0-n之间的每个值。这是低效的，并且不能总是处理大的n数。获取第一个未知变量的最佳方法是什么

def sol_equa(n):
    answers = []
    for x in range(1 , n+1):
        y = ((x ** 2 - n) / 4) ** (1 / 2)
        try:
            if y == y // 1:
                answers.append([x, int(y)])
        except TypeError:
            continue
    if len(answers) >= 1:
        answers = list(reversed(answers))
        return answers
    else:
        return []

sol_equation(90005) --> "[[45003, 22501], [9003, 4499], [981, 467], [309, 37]]"

Answer 1

您可以使用^{}。把你的方程取为

from sympy.solvers.diophantine import diophantine
from sympy.abc import x,y

n = 90005
solutions = diophantine(x**2 - 4*y**2 - n)
print(solutions)
#{(-981, 467), (-309, 37), (45003, 22501), (-45003, -22501), (309, -37), (-9003, -4499), (981, 467), (9003, -4499), (-9003, 4499), (45003, -22501), (309, 37), (-309, -37), (-45003, 22501), (9003, 4499), (981, -467), (-981, -467)}

如果只需要正解，可以使用set comprehension：

positive_solutions = {sol for sol in solutions if sol[0] > 0 and sol[1] > 0}
print(positive_solutions)
#{(981, 467), (9003, 4499), (309, 37), (45003, 22501)}

执行时间测试

from timeit import timeit

sol_equa= '''
def sol_equa(n):
    answers = []
    for x in range(1 , n+1):
        y = ((x ** 2 - n) / 4) ** (1 / 2)
        try:
            if y == y // 1:
                answers.append([x, int(y)])
        except TypeError:
            continue
    if len(answers) >= 1:
        answers = list(reversed(answers))
        return answers
    else:
        return []
sol_equa(90005)
'''

sympy_solver = '''
def sympy_solver(n):
    solutions = diophantine(x**2 - 4*y**2 - n)
    return {sol for sol in solutions if sol[0] > 0 and sol[1] > 0}
sympy_solver(90005)
'''

setup = '''
from sympy.solvers.diophantine import diophantine
from sympy.abc import x,y
'''

print(timeit(sympy_solver,number=1000, setup = setup))
#13.50360608200208

print(timeit(sol_equa,number=1000))
#I don't know, it took too long :P