정사각형

Question

프로젝트 오일러 문제 27 (https://projecteuler.net/problem=27)에 대해 묻습니다. 나는 작동하지 않거나 충분히 빠르게 작동하지 않는 코드를 작성했습니다. 프로그래밍에 익숙하지 않고받은 오류의 의미를 완전히 이해하지 못합니다.

어쨌든, 질문에 정수 $ a, b $와 $ | a |, | b | < 1000 $ $ n^2 + an + b $ $ n = 0 $로 시작하는 연속 소수의 가장 큰 모음을 만듭니다. 우선, 우리는 $ b $가 프라임 (prime)이어야하고 $ n = 0 $ 항이 프라임 (prime)이고 체인을 시작해야한다는 것을 알게됩니다. 그러므로 가능한 모든 소수 값에 대해 b를 반복 한 코드를 작성한 다음 각각의 정수 $ -1000 < < 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보다 커야합니다. b. 그러나 a와 b의 가능한 범위는 너무 작으므로 이러한 제약 조건을 찾아서 솔루션에 통합 할 가치가 없습니다. 실수를하고 발을 쏠 수있는 추가 기회 만 생성합니다.

고려해야 할 유일한 제한은 n이 b의 배수이면 n^2 + a*n + b은 n으로 나눌 수 있어야한다는 것입니다. 따라서 소수의 연쇄는 늦어도 n = b에서 멈춰야 만하며, 이는 소수성을 검사해야 할 가능성이있는 최대 숫자에 대한 한도를 제공합니다. 말하자면, 소수 테스트의 가능한 가장 큰 후보는 2,000,000 미만이어야합니다. 소수성 테스트로 시험 분할 대신 집합 멤버십을 사용할 때 이것은 유용한 제한을 제공합니다.

로섬은 코멘트에서 힌트를 얻었으므로 마지막으로 테스트 한 계수 세트와 결과 체인 ​​길이를 찾지 않아야합니다. 가장 긴 사슬 체인을 제공하는 계수 a와 b를 찾고 해당 쌍의 곱을 인쇄해야합니다. 따라서 '체인 테스트'와 그 결과를 처리하는 방식을 변경해야합니다. 당신이 조금을 정리하고 중복을 제거하는 경우

은 아마 당신은 더 나은 코드를 이해하게 될 것입니다 (예를 들어 is_prime(x)는 x >= 2 따라서 x > 0을 의미, 그것은 단지 소수성에 대한 테스트 후 적극성에 대한 테스트를 넣어 이해가되지 않습니다) . 또한 코드를 리팩터링하여 개별 비트와 조각이 단 하나의 책임을지며 전체 세방에 통합되기 전에 별도로 테스트/튜닝 될 수 있도록해야합니다.

작업 모양으로 코드를 가져 오면 Code Review에 게시하고 싶을 수 있습니다. 이는 찾고있는 의견의 유형에 훨씬 적합합니다.

P .: 내가 처음에 언급 한 것과 같은 제약 조건은 실제로 봉투를 밀어 넣으려고 할 때 매우 흥미로워 지지만 문제를 해결하기 위해서는 가능한 가장 간단한 해결책을 찾는 것이 가장 좋습니다. 파이썬에서도 2 분의 1 초도 걸리지 않습니다.