[C/C++] 프로젝트 오일러 #27 : 2차식 소수 생성

Project Euler #27 “Quadratic Primes” 문제는 다음을 요구합니다:

주어진 이차식  \(n^2 + an + b\) 에서  n 은 0부터 시작하는 정수이고,  a 와  b 는 정수 범위  |a| < 1000 ,  |b| < 1000 를 만족하는 값입니다. 이 이차식이 생성하는 연속된  n  값에 대해 소수를 만들어내는 최대 길이를 가진  a 와  b 를 찾고, 그 값의 곱  \(a \times b\) 를 계산하는 것이 목표입니다.

요약:
1.  \(n^2 + an + b\) 가 연속된  n 에 대해 최대한 많은 소수를 생성하도록 하는  a 와  b 를 찾는다.
2. 그런  a 와  b 의 곱을 구한다.

 

\( n^2 + n + 41 \) 식은 너무나도 유명한 2차식 소수 생성 공식입니다.  n의 값이 0부터 39까지 총 40개의 연속된 소수를 생성합니다.

더 많은 소수를 내기 위해서는 더 큰 숫자가 필요하겠죠.  일단 문제에 있는 것을 조금 더 보자면,
\[ n^2 + an + b \quad \text{where} \quad |a| < 1000 \quad \text{and} \quad |b| < 1000 \]
란 조건을 조금 더 줄일 필요가 있습니다.  n = 0 일 때 위 식이 소수가 되기 위해서는 b 는 반드시 소수여야 합니다.  그러므로 b가 소수가 아니라면, a가 어떤 값이라도 원하는 답이 될 수가 없습니다.

b가 소수라면, a는 -b보다 큰 수여야 하고, 홀수여야 합니다.  |a|가 짝수라면, n이 홀수인 항에 대해서는 위 식은 반드시 짝수가 되어버립니다.  그러므로 |a|는 홀수여야 합니다.

매번 소수를 검사하는 것보다는 충분히 큰 숫자 범위안에 소수를 찾아놓고, 소수 검사비용을 줄였습니다.  동적 프로그래밍을 이용하여도 되겠지만, 여기서는 소수집합을 잡아놓고 시작했습니다.

 

generating prime numbers

소스는 참고용으로만 봐주세요.

//------------------------------------------------
//    Project Euler #27 - Quadratic Primes
//        - by Aubrey Choi
//        - created at 2015-10-15
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

void getprimes(unsigned char primes[], int limit);

int main()
{
    unsigned char primes[20000/8];

    memset(primes, 0, sizeof(primes));
    getprimes(primes, 20000);

    int max = 0;
    int maxa, maxb;

    for( int b = 3 ; b < 1000 ; b += 2 )
    {
        if( !(primes[b/8] & (1<<(b%8))) ) continue;

        for( int a = -b ; a < 1000 ; a += 2 )
        {
            int n;
            for( n = 1 ; ; n++ )
            {
                int c = n*n + a*n + b;
                if( c <= 0 ) break;
                if( !(primes[c/8] & (1<<(c%8))) ) break;
            }
            if( max < n )
            {
                max = n;
                maxa = a;
                maxb = b;
            }
        }
    }
    printf("Ans = %d(a = %d, b = %d, max = %d)\n", maxa*maxb, maxa, maxb, max);
}

void getprimes(unsigned char primes[], int limit)
{
    primes[0] = 4;
    for( int i = 3 ; i < limit ; i += 2 )
    {
        int j;
        for( j = 3 ; j*j <= i && (i%j) ; j+=2 ) ;
        if( j*j > i ) primes[i/8] |= 1<<(i%8);
    }
    return;
}