[C/C++] 프로젝트 오일러 #111 Primes with Runs(히스토그램)

프로젝트 오일러 문제 111번, “Primes with Runs”는 소수와 숫자 패턴의 반복성을 중심으로 하는 문제입니다. 이 문제는 자리수가 m인 숫자 집합을 대상으로 합니다. 예를 들어 m이 4라면, 4자리 숫자인 1000에서 9999까지의 숫자를 다루게 됩니다.

문제의 주요 관심사는 자리수가 m인 숫자 중에서 특정 숫자가 반복적으로 나타나는 패턴을 찾는 것입니다. 여기서 “반복”은 특정 숫자가 얼마나 많이 나타나는지를 의미합니다. 예를 들어, 4자리 숫자 3331에서는 숫자 3이 세 번 반복됩니다. 이러한 숫자 중에서도 소수인 숫자만을 대상으로 합니다. 소수란 1과 자기 자신만으로 나누어떨어지는 숫자이므로, 여기서 다루는 숫자가 소수인지 확인하는 과정이 필수적입니다.

각 숫자 집합에 대해 가장 많이 반복되는 숫자를 먼저 찾습니다. 그리고 그 반복을 만족하는 숫자들 중에서 소수인 것들을 골라냅니다. 마지막으로, 이렇게 선택된 소수들의 합계를 계산하는 것이 문제의 목표입니다. 예를 들어, 4자리 숫자에서 2가 가장 많이 반복되는 소수를 찾으라는 조건이 주어진다면, 2221이나 1223과 같은 숫자들을 확인하고, 이러한 소수들의 합을 구하게 됩니다.

이 문제는 자리수가 큰 경우(예: m=10)에도 적용됩니다. 따라서 숫자를 생성하고 반복 조건을 검사하며, 동시에 소수 여부를 확인하는 과정이 매우 효율적으로 이루어져야 합니다. 특히 자리수가 커질수록 계산량이 급격히 증가하기 때문에, 알고리즘 설계에서 성능 최적화가 중요한 문제입니다.

 

prime pattern

 

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #111 - Primes with Runs
//        - by Aubrey Choi
//        - created at 2015-03-28
//------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include "isprime.h"

int main()
{
    int k = 10;
    int pc[10];
    int md[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1 };
    uint64_t sum[10];
    uint64_t s = 1;

    memset(pc, 0, sizeof(pc));
    memset(sum, 0, sizeof(sum));
    for( int i = 1 ; i < k ; i++, s *= 10 );
    for( uint64_t i = s+1 ; i < s*10 ; i += 2 )
    {
        int r[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        uint64_t q = i;
        while( q ) { r[q%10]++; q /= 10; }
        bool needCheck = false;
        for( int d = 0 ; d < 10 ; d++ )
            if( md[d] <= r[d] ) { needCheck = true; break; }
        if( needCheck == false ) continue;
        if( isPrime(i) == false ) continue;
        for( int d = 0 ; d < 10 ; d++ ) 
        {
            if( md[d] > r[d] ) continue;
            if( md[d] < r[d] ) { md[d] = r[d]; pc[d] = 1; sum[d] = i; }
            else { pc[d]++; sum[d] += i; }
        }
    }

    uint64_t ans = 0;
    for( int d = 0 ; d < 10 ; d++ )
    {
        printf("%d : %4d %4d %8ju\n", d, md[d], pc[d], sum[d]);
        ans += sum[d];
    }
    printf("ans = %ju\n", ans);
}

 

m자리 숫자에서 각 숫자(0~9)가 반복적으로 나타날 때, 소수인 경우의 합계를 계산하는 내용을 구현하고 있습니다.

1. 초기 변수 선언 및 초기화

int k = 10;
int pc[10];
int md[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1 };
uint64_t sum[10];
uint64_t s = 1;

memset(pc, 0, sizeof(pc));
memset(sum, 0, sizeof(sum));

여기에서 k는 자리수를 나타내며, 10자리 숫자를 대상으로 계산하겠다는 의미입니다. 배열 pc는 각 숫자가 특정 반복 조건을 만족하는 소수의 개수를 저장하기 위한 용도로 사용됩니다. md는 각 숫자(0~9)가 자리수 내에서 나타날 수 있는 최대 반복 횟수를 추적합니다. sum은 각 숫자에 대해 해당 조건을 만족하는 소수들의 합을 저장합니다. 마지막으로, s는 m자리 숫자의 하한을 계산하기 위해 사용됩니다. 예를 들어, s는 \( 10^9 \) 로 초기화됩니다.

memset은 배열을 초기화하는 함수로, pc와 sum 배열의 모든 요소를 0으로 설정합니다.

2. 숫자 생성과 반복 확인

for( int i = 1 ; i < k ; i++, s *= 10 );
for( uint64_t i = s+1 ; i < s*10 ; i += 2 )
{
    int r[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    uint64_t q = i;
    while( q ) { r[q%10]++; q /= 10; }

이 코드는 m자리 숫자의 범위를 설정하고, 홀수 숫자만 검사합니다. s는 m자리 숫자의 시작점(\(10^9\))을 나타내며, s*10은 m+1자리 숫자의 시작점이 됩니다.

내부 반복문에서 숫자 i를 10으로 나누어가며 각 자릿수의 숫자를 카운트하여 배열 r에 저장합니다. 예를 들어, 숫자 1123456789가 들어오면 r[1]=2, r[2]=1, …, r[9]=1이 됩니다. 이 배열은 각 숫자의 반복 횟수를 기록합니다.

3. 소수 여부와 조건 확인

bool needCheck = false;
for( int d = 0 ; d < 10 ; d++ )
    if( md[d] <= r[d] ) { needCheck = true; break; }
if( needCheck == false ) continue;
if( isPrime(i) == false ) continue;

숫자 i에 대해, needCheck는 반복 횟수 조건을 만족하는 숫자가 있는지를 확인합니다. 만약 md[d]가 해당 숫자 d의 반복 횟수 r[d]보다 작거나 같다면, 이 숫자는 검사 대상이 됩니다. 조건을 만족하지 않으면 다음 숫자로 넘어갑니다.

isPrime(i) 함수는 숫자 i가 소수인지 확인하며, 소수가 아니라면 역시 넘어갑니다.

4. 반복 횟수와 소수 합계 업데이트

for( int d = 0 ; d < 10 ; d++ ) 
{
    if( md[d] > r[d] ) continue;
    if( md[d] < r[d] ) { md[d] = r[d]; pc[d] = 1; sum[d] = i; }
    else { pc[d]++; sum[d] += i; }
}

이 부분은 각 숫자(0~9)에 대해 최대 반복 횟수를 추적하고, 조건을 만족하는 소수의 개수와 합계를 업데이트합니다.

만약 새로운 숫자에서 숫자 d의 반복 횟수가 현재 최대 반복 횟수보다 크다면, 이를 갱신하고 해당 소수의 합계와 개수를 초기화합니다. 만약 반복 횟수가 같다면, 개수를 증가시키고 합계를 누적합니다.

5. 결과 출력

uint64_t ans = 0;
for( int d = 0 ; d < 10 ; d++ )
{
    printf("%d : %4d %4d %8ju\n", d, md[d], pc[d], sum[d]);
    ans += sum[d];
}
printf("ans = %ju\n", ans);

이 코드는 최종 결과를 출력합니다. 각 숫자(0~9)에 대해 최대 반복 횟수(md[d]), 조건을 만족하는 소수의 개수(pc[d]), 그리고 해당 소수들의 합계(sum[d])를 출력합니다. 마지막으로, 모든 숫자에 대한 소수 합계를 계산하여 ans에 저장하고 출력합니다.

주요 함수와 동작 개요

1. 프로그램은 자리수가 m인 숫자 집합을 생성합니다.
2. 각 숫자에 대해 자릿수별 반복 횟수를 계산합니다.
3. 반복 조건을 만족하는 숫자가 소수인지 확인합니다.
4. 조건을 만족하는 소수들의 개수와 합계를 계산합니다.
5. 최종적으로 각 숫자에 대한 결과와 전체 합계를 출력합니다.

이 코드에서 가장 중요한 부분은 숫자를 효율적으로 생성하고, 반복 횟수 조건과 소수 여부를 빠르게 확인하는 로직입니다.