501. 프로젝트 오일러 #501 : 약수의 갯수가 8개인 수 찾기

그동안 프로젝트 오일러 문제를 1번부터 차례대로 풀다가, 좀 지겹다는 생각이 들더군요.

현재까지는 32개의 문제를 차례대로 풀어나갔는데요.

과연 뒤에 있는 문제들은 어떨까 생각이 들어서 찾아보았습니다.

뒤에 있는 문제는 도저히 일반적인 방법으로 풀지 못 하는 것들이네요.

정답자도 십여명이고...

일단 도전하기로 했는데, 이 문제는 소수의 갯수를 알아야 풀 수 있는 문제인지라, 상당히 어렵네요.  숫자의 범위가 작으면 어떻게든 풀겠지만요.

앞에 있는 문제가 실제 프로그램 돌렸을 때, 1초 이내에 나온 것에 비해서, 이 문제는 며칠 이상이 걸릴 문제네요.

소수의 갯수는 숫자가 커지면, 그에 정비례는 아니지만, 꾸준하게 증가합니다.

약수의 갯수가 8개인 수들도 꾸준하게 증가하는데, 그 숫자의 증가속도가 좀 빠릅니다.

일단 약수의 갯수가 8개인 수들은 다음과 같은 법칙이 있습니다.

서로 다른 소수 이 있다면, 다음과 같은 경우에만 약수의 갯수가 8개가 됩니다.

이 이외에는 약수의 갯수가 8개인 경우는 발생하지 않습니다.

숫자의 범위가 이기 때문에 일일이 숫자를 돌아가면서 약수의 갯수를 구하려면, 아주 많은 시간이 소모될겁니다.  대충 제 컴퓨터에서 계산한 결과로는 1년이 넘게 걸리네요.

이것은 현실적이라고 생각되지 않아서, 일단 소수의 갯수를 먼저 구하도록 했습니다.

가장 작은 소수는 2, 3 이기 때문에, 2를 3승한 8과 2와 3을 곱한 6이 가장 큰 문제입니다.  이 숫자들은 해당 범위안에 있는 대부분 소수와 곱해도 해당 수를 벗어나지 않기 때문입니다.  그래서 정도까지의 소수의 갯수를 구하도록 했습니다.  구글에서 "number of primes" 하면, 이 숫자들은 잘 나와있습니다.  울프람 사이트 가셔도 되고요.

그런데, 이것만으로는 속도를 빠르게 하기 힘드네요.  참고로 까지의 약수가 8개인 수 찾는데 걸리는 시간이 제 노트북에 VM위의 우분투 서버에서 무려 51초가 걸리네요.  소수를 검사하는 비용을 최대한 줄이고, 절대 나올 수 없는 패턴을 제거했는데도 워낙 알고리즘 자체가 더 나아질 수 없는 상황이네요.

그래서 좀 작은 단위로 소수의 갯수 을 구하는 방법을 시도하고 있습니다.  백만 범위안에서는 아주 빠른 시간안에 소수의 갯수를 찾고 있어서 현재는 4백만 범위씩 잘라서 6만개정도의 소수의 갯수를 찾고 있습니다.

소수의 갯수를 한번에 다 찾는 것은 어렵기 때문에 파일 입출력을 이용해서 계속 증가시키면서 찾도록 프로그램을 작성했습니다.  아마 다 찾는데 며칠 소요될 듯 하네요.

#include <stdio.h>
#include <stdint.h>

uint64_t pi[65536];
int picount;

void loadpi();
void savepi();
bool isPrime(uint64_t n);

int main()
{
    loadpi();
    for( int i = 0; i < 65536 ; i++ )
    {
        if( pi[i] ) continue;
        int sum = i?pi[i-1]:1;
        for( uint64_t j = (i<<24)+(i?1:3) ; j <= ((i+1)<<24) ; j += 2 )
            if( isPrime(j) ) sum++;
        pi[i] = sum;
        printf("pi[%d] = %d\n", i, sum);
        picount = i+1;
        savepi();
    }
}

void loadpi()
{
    FILE *fi = fopen("pi.dat", "rb");
    if( fi == NULL ) return;
    picount = fread(pi, sizeof(uint64_t), 65536, fi);
    fclose(fi);
}

void savepi()
{
    FILE *fi = fopen("pi.dat", "wb");
    if( fi == NULL ) return;
    fwrite(pi, sizeof(uint64_t), picount, fi);
    fclose(fi);
}