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|\le 1000$로 제한한다.

2. 구현: ver 1.0

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

# -*- 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이다.