58. 프로젝트 오일러 #58 : 나선형 소수들

#58 문제도 난이도는 5% 문제입니다.

문제 자체는 복잡해 보여도 사실 푸는데 전혀 어려움이 없는 문제예요.

문제는 1부터 차례대로 나선형으로 수들을 배치하게 되면, 대각선쪽에는 홀수가 항상 배치되게 됩니다.  그럴 경우, 대각선에 있는 홀수 중 소수의 비율이 얼마일것인가가 이 문제를 푸는데 중요한 부분입니다.

이 문제는 소수의 비율이 10% 미만으로 떨어질 때, 한 변에 위치하는 수들의 갯수를 답하라는 것입니다.

배치하는 방법이 일정하기 때문에, 대각선에 위치한 숫자들의 순열만 파악하면 됩니다.

일단 첫번째 대각선(가장 작은 수)의 수열은 다음과 같이 표현할 수 있습니다.  s를 한변 길이의 절반이라고 할 때(즉, 1이 위치한 s는 0, 그 다음은 1, 그 다음은 2.. ),

이 것을 이용하여, 다음 수는 2s, 4s, 6s 만큼 더해주면 되겠죠.

이것을 단순하게 프로그램하면 아래와 같습니다.

void solve1()
{
    int64_t s, pcount = 0;
    for( s = 1 ;  ; s++ )
    {
        int64_t f = 4*s*s - 2*s + 1;
        if( isPrime(f) ) pcount++;
        if( isPrime(f+2*s) ) pcount++;
        if( isPrime(f+4*s) ) pcount++;
        if( isPrime(f+6*s) ) pcount++;
        if( pcount*10 < s*4+1 ) break;
    }
    printf("Ans = %I64d\n", s*2+1);
}