Daily Algorithm - Day 26

Quadratic Primes

Euler discovered the remarkable quadratic formula:

$n^2 + n + 41$

It turns out that the formula will produce $40$ primes for the consecutive integer values
$0 \le n \le 39$. However, when $n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41$ is divisible by $41$, and certainly when $n = 41, 41^2 + 41 + 41$ is clearly divisible by $41$.

The incredible formula $n^2 - 79n + 1601$ was discovered, which produces $80$ primes for the consecutive values $0 \le n \le 79$. The product of the coefficients, $-79$ and $1601$, is $-125479$.

Considering quadratics of the form:
$n^2+an+b$, where $|a| < 1000$ and $|b| \le 1000$
($|n|$ is the modulus/absolute value of $n$)

Find the product of the coefficients, $a$ and $b$, for the quadratic expression that produces the maximum number of primes for consecutive values of $n$, strating with $n=0$

$n^2 + an + b$ (단 $| a | < 1000, | b | < 1000$) 의 모양을 가진 이차식 중에서 $0$부터 시작하는 연속된 $n$에 대해 가장 많은 소수를 만들어내는 이차식을 찾아서, 그 계수 $a$와 $b$의 곱을 구하는 문제이다.

내가 생각한 구현 방식은 다음과 같다.

1. 소수인지 판별해주는 함수를 작성한다.
2. 반복문을 통해 모든 $a, b$를 대입한 함수에 대하여 연속하여 $n$이 소수로 나오는 함수를 찾아낸다.

먼저 소수인지 판별해주는 함수다. 이전에 여러번 작성해봤지만 이번에는 소수를 구하는데 들어가는 계산을 최대한 줄여보려고 한다. 2를 제외한 짝수는 모두 소수가 아님을 이용하자.

//Python
''' 기존 방식
def is_prime(n):
    if n <= 1: # 1 이하의 숫자는 소수가 아님
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
'''

def is_prime(n):
    if n <= 1: # 1 이하의 숫자는 소수가 아님
        return False
    if n == 2: # 2는 소수
        return True
    if n % 2 == 0: # 2를 제외한 모든 짝수는 소수가 아님
        return False
    for i in range(3, int(n**0.5) + 1, 2): # 3~루트n인 홀수만 검사
        if n % i == 0:
            return False
    return True

기존 방식에 비해 계산횟수를 절반 정도로 줄일 수 있었다.

다음은 반복문을 통해 가장 길게 연속되는 $n$을 찾아내서 계수 $a,b$의 곱을 출력해주는 함수다.

# a,b의 절대값이 x이하인 이차식 n^2+an+b에 대하여 계산해준다.
def solution(x):
	#필요한 변수를 초기화
    best_length = 0
    result = 0
    
    for a in range (-x, x + 1):
        for b in range (-x, x + 1):
            if (is_prime(b)):  # b가 소수가 아니라면 n=0일 때 소수가 나오지 않는다.
                n = 0
                while True:
                    quad = n**2 + a*n + b
                    if not is_prime(quad):  # 이차식의 결과가 소수가 아니라면 break
                        break
                    n += 1
                if n > best_length:  # 현재 연속되는 n의 길이가 가장 길면 
                    best_length = n
                    result = a * b
            else:  # b가 소수가 아니므로 다음 숫자로
                continue
            
    return result

print(solution(1000))

>>> -59231   #correct

그렇다면 다음은 코드 리뷰다.

• 개선된 코드

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def solution(x):
    best_length = 0
    result = 0
    
    # 가능한 a와 b 값에 대해 반복
    for a in range(-x, x + 1):
        for b in range(-x, x + 1):
            if is_prime(b):  # b가 소수일 경우에만 계산
                n = 0
                while True:
                    quad = n**2 + a*n + b  # 2차 방정식 계산
                    if not is_prime(quad):  # 계산된 값이 소수가 아니면 종료
                        break
                    n += 1  # 소수라면 n을 증가시켜 계속 계산
                if n > best_length:  # 가장 긴 소수 시퀀스 길이가 발견되면
                    best_length = n
                    result = a * b  # a * b 값을 저장
    return result

print(solution(1000))

전반적으로 좋은 리뷰지만, gpt도 만능은 아니라는걸 깨달을 수 있었다. is_prime의 개선점을 코드에 적용하지 않았고, 3번 지적인 이차식을 매번 계산하고 있으니 최적화하면 더 효율적일 수 있다는 부분은 문제 특성상 적용이 불가능해 보인다. 그래서 개선된 코드엔 else-continue 부분과 주석 수정을 제외하고는 바뀐 점이 없다. 그래서 이를 gpt에게 물어보니 다음과 같은 답을 얻을 수 있었다.

그렇게 나온 코드는 다음과 같다.

def sieve_of_eratosthenes(limit):
    """에라토스테네스의 체를 이용해 소수를 미리 계산"""
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False  # 0과 1은 소수가 아님
    for start in range(2, int(limit ** 0.5) + 1):
        if sieve[start]:
            for i in range(start * start, limit + 1, start):
                sieve[i] = False
    return sieve

def is_prime_with_sieve(n, sieve):
    """미리 계산된 소수 리스트(sieve)를 사용한 소수 판별"""
    if n < len(sieve):
        return sieve[n]
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def solution(x):
    """n^2 + an + b 방정식이 가장 긴 소수 연속성을 가지는 a*b 계산"""
    prime_limit = max(1000, x**2 + x + 41)  # 충분히 큰 소수 리스트 범위 설정
    sieve = sieve_of_eratosthenes(prime_limit)  # 소수 리스트 생성
    
    best_length = 0
    result = 0
    
    for a in range(-x, x + 1):
        for b in range(-x, x + 1):
            if is_prime_with_sieve(b, sieve):  # b가 소수인지 확인
                n = 0
                while True:
                    quad = n**2 + a*n + b
                    if quad < 0 or not is_prime_with_sieve(quad, sieve):  # 음수나 소수가 아닐 경우 종료
                        break
                    n += 1
                if n > best_length:  # 가장 긴 연속 소수 길이 갱신
                    best_length = n
                    result = a * b
    return result

# 실행 예시
print(solution(1000))

오늘은 여기까지
-2025.01.16-