27. Quadratic primes

1. 개요

문제는 이곳에서 확인할 수 있다. 어떤 정수 \(a\), \(b\)가 주어졌을 때, Quadratic form \(n^2+an+b\)는 \(n=0\)부터 시작하여 소수를 연속적으로 생성한다. 예를 들어 \(n^2+n+41\)은 40개의 소수를, \(n^2-79n+1601\)은 80개의 소수를 생성한다. 소수를 연속적으로 가장 많이 생성하는 \(a\)와 \(b\)를 찾고 그 곱을 구하는 것이 목표이다. 단, \(a\), \(b\)를 \(\left| a\right|<1000\) 그리고 \(\left| b\right|\leq 1000\)로 제한한다.

2. 구현: ver 1.0

Quadratic form의 결과가 소수인지 파악하기 위해서, 소수를 담은 리스트를 만든다. 

# -*- coding: utf-8 -*-
import math as m


class Prime(object):
    """충분한 길이의 소수를 담고 필요한 경우 소수를 더 찾는다."""
    def __init__(self):
        self.prime_list = [2, 3]

    def make_prime_list(self):
        prime_value = self.prime_list.pop()
        prime_candidate_list = list(range(prime_value, prime_value*2, 2))
        lim = m.sqrt(prime_value * 2)
        i = 0

        while True:
            self.prime_list.append(prime_candidate_list.pop(0))
            i += 1
            prime_value = self.prime_list[i]
            prime_candidate_list = [p for p in prime_candidate_list
                                    if p % prime_value != 0]

            if prime_value > lim:
                break

        self.prime_list.extend(prime_candidate_list)


def quadratic_formula(n, a, b):
    """소수를 생성하는 식"""
    return n**2 + a*n + b

p = Prime()
max_prime_length = 0

for a in range(-999, 1000):
    for b in range(-1000, 1001):

        n = 0
        prime_length = 0

        while True:
            q_prime = quadratic_formula(n, a, b)

            # quadratic foumula의 결과가 지금까지 찾은 가장 큰 소수보다 작아야 한다.
            while q_prime > p.prime_list[-1:][0]:
                p.make_prime_list()

            if q_prime not in p.prime_list:
                break

            n += 1
            prime_length += 1

        if max_prime_length < prime_length:
            max_prime_length = prime_length
            answer = a*b
            print('a: ', a, ', b: ', b, ', length: ', max_prime_length, 
                  ', answer: ', answer)

        if a % 500 == 0 and b % 500 == 0:
            print('now, a: ', a, ', b: ', b)

print(answer)

답은 -59231이다.