27. 프로젝트 오일러 #27 : 2차식 소수 생성

2차식을 이용해서 소수를 생성하기 위한 2차식 파라미터를 찾는 프로그램입니다.

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

더 많은 소수를 내기 위해서는 더 큰 숫자가 필요하겠죠.  일단 문제에 있는 것을 조금 더 보자면,

란 조건을 조금 더 줄일 필요가 있습니다.  n = 0 일 때 위 식이 소수가 되기 위해서는 b 는 반드시 소수여야 합니다.  그러므로 b가 소수가 아니라면, a가 어떤 값이라도 원하는 답이 될 수가 없습니다.

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

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

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

#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;
}