Квадратичные числа

Question

Я спрашиваю о проблеме Project Euler 27 (https://projecteuler.net/problem=27). Я написал фрагмент кода, который либо не работает, либо не работает достаточно быстро - я новичок в программировании и не совсем понимаю смысл ошибки, которую я получаю.

В любом случае, вопрос просит меня найти, какие целые числа $ a, b $ с $ | a |, | b | < 1000 $ приводит к $ n^2 + an + b $, производящему самую большую коллекцию последовательных простых чисел, начиная с $ n = 0 $. Прежде всего заметим, что $ b $ должен быть простым, чтобы член $ n = 0 $ был простым и начинал цепочку. Поэтому я написал фрагмент кода, который зацикливает b на все возможные простые значения, а затем проверяет каждое целое число $ -1000 < a < 1000 $ и измеряет длину цепочки последовательных простых чисел. Я включил его ниже:

n=int(input("Set a bound for range of a and b: ")) 


def is_prime(n): 
if n==1: 
    return False 
elif n==2 or n==3: 
    return True 
elif (n % 2 == 0) or (n % 3 == 0): 
    return False 
elif all(n % i != 0 for i in range(2, ceil(n**0.5+1))): 
    return True 
else: 
    return False 

def seive(n): 
primes=[] 
for i in range(n): 
    if is_prime(i)==True: 
     primes.append(i) 
for j in primes: #j can't be allowed to be negative since when m=0 (the first term), we must have m**2+k*m+j prime. Therefore j must be chosen from primes 
    for k in range(-n,n,1): 
     chain=[] 
     for m in range(0,n): 
      while is_prime(m**2+k*m+j) == True and m**2+k*m+j>0: 
       chain.append(m**2 + k*m + j) 
       details = [j,k,len(chain)] 
return details 

print(seive(n)) 

Может кто-то пожалуйста, либо объяснить, что я сделал неправильно, и дать мне подсказку о том, как получить это работает? Благодаря!

Answer 1

Анализ проблемы дает несколько ограничений, таких как, например, что b должно быть простым или a должно быть больше 1 - b. Однако возможный диапазон для a и b настолько крошечный, что не стоит искать такие ограничения и включать их в решение - это только создает дополнительные возможности для совершения ошибок и стрельбы в ногу.

Единственное ограничение, заслуживающее рассмотрения, состоит в том, что n^2 + a*n + b должно делиться на n, когда n кратно b. Следовательно, цепочка простых чисел должна останавливаться при n = b не позднее, что дает потолок для максимально возможного числа, которое, возможно, нужно будет проверить на простоту. То есть, наибольший возможный кандидат для теста на первичность должен быть менее 2 000 000. Это дает полезный предел при использовании набора членов вместо пробного деления в качестве теста на первичность.

Как указано в комментариях, задача заключается не в том, чтобы найти последний проверенный набор коэффициентов и результирующую длину цепи. Вас попросят найти коэффициенты a и b, которые дают самую длинную цепочку простых чисел, и распечатать произведение этой пары. Следовательно, вам нужно изменить способ обработки «цепного теста» и его результатов.

Возможно, вы поймете код лучше, если вы очистите его немного и удалить избыточность (например is_prime(x) подразумевает x >= 2 и, следовательно, x > 0, он просто не имеет смысла ставить тест на положительность после теста на простоту) , Также должно быть полезно реорганизовать код, чтобы отдельные биты и части имели только одну единственную ответственность и могут быть проверены/настроены отдельно, прежде чем быть интегрированы во весь shebang.

Как только вы получили свой код в рабочей форме, вы можете его опубликовать на Code Review, что является гораздо более подходящим местом для тех видов обратной связи, которые вы, похоже, ищете.

P.S .: ограничения, подобные тем, о которых я упоминал в начале, очень интересны, когда вы пытаетесь нажать на конверт, но для решения проблемы, как указано, лучше всего пойти на самое простое решение. Это не должно занимать больше нескольких секунд даже в Python.