[PE] Project Euler 27

프로젝트 오일러 27번에 처음 접근하면서 이거 나이브하게 풀어도 풀릴까 테스트 먼저 해보자고 생각하고 달려들었는데 바로 풀려버려서... 문제는 n^2 + a*n + b 꼴의 함수가 주어졌을때, 절댓값 1000 이하의 두 정수 a, b를 선택하여 n=0부터 i 이하의 숫자들을 대입했을 때 전부 소수가 되도록 하는 최대 i의 값이 최대가 되도록 하는 것이다. 즉, (a, b) 쌍에 대해 i가 결정되는데, 이 i값을 최대로 만드는 (a, b)쌍을 구하는 것.

 

나이브한 방법으로 풀 때에는 다음의 아이디어만 있어도 충분하다.

- 어떤 수가 소수인지 판별하기 위해서는 2부터 그 수의 제곱근 이하의 모든 자연수에 대하여 나눠보면 된다.

- 조금 탐색 공간을 줄이고 싶다면, n=0을 대입했을 때 값이 b가 되므로, b가 소수여야 한다.

 

문제를 풀 때는 두 번째 아이디어를 적용하기 귀찮아서 b가 음수일 경우 n=0일때 소수가 되지 않을테니 b가 음이 아닌 정수라는 조건 정도만 걸어두었다.

 

그리고 p_test 함수에서는 n이 2보다 작으면 소수가 아니므로 바로 false값을 리턴하게 하였다.

def p_test(n):
    if n<2: return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0: return False
    return True
 
sol = -1
sol_x = (-1,-1)
for a in range(-1000, 1001):
    for b in range(0, 1001):
        x = 0
        while 1:
            if p_test(x*x+a*x+b):
                x+=1
            else:
                break
        if x>sol:
            sol=x
            sol_x=(a,b)
 
print(sol_x)
a,b = sol_x
print(a*b)

이 정도 만으로 계산 시간 그리 오래 걸리지 않고(10초 미만..?) 원하는 답을 얻을 수 있다.