Project Euler - Problem 12

昨天在 TOSSUG 聚會上 Choupi 提到這個問題 Project Euler - Problem 12 於是就寫了以下的 Vala 程式碼來解這個問題

void main()
{
    int i = 0, number = 0;
    // 用來儲存質數分解的結果
    HashTable<string, int*> factors = null;

    do {
        // 逐個取出三角數
        number = triangle_number(++i);
        // 算出所有因數的個數直到比 500 還要大為止
    } while (factor_number_of(number, out factors) < 500);

    // 把算出來的答案印出來
    stdout.printf("Answer: %d\n", number);

    // 將答案驗算一遍
    print_factors(factors);
}

void print_factors(HashTable<string, int*> factors)
{
    int number = 1;

    List<unowned string> keys = factors.get_keys();
    // 把質因數表的鍵值依照數值大小重新排序
    keys.sort( (a, b) => {
        int num1 = int.parse(a);
        int num2 = int.parse(b);
        if (num1 < num2 ) {
            return -1;
        }
        else if (num1 > num2) {
            return 1;
        }
        else {
            return 0;
        }
    });

    // 驗算過程
    foreach (unowned string key in keys) {
        int* count = (int*) factors.lookup(key);
        int prime = int.parse(key);
        if (*count > 1) {
            stdout.printf("%d^%d*", prime, *count);
        }
        else {
            stdout.printf("%d*", prime);
        }
        // 重覆乘上質因數出現的次數
        for (int i = 0; i < *count; i++) {
            number = number * prime;
        }
        free(count);
    }

    stdout.printf("\b=%d\n", number);
}

// 三角數的計算
int triangle_number(int num)
{
    return num * (num + 1) / 2;
}

// 找出某數值的質因數分解
int factor_number_of(int number, out HashTable<string, int*> table)
{
    table = new HashTable<string, int*>(str_hash, str_equal);
    do {
        // 找出該數值的平方根
        int root = sqrt_floor_of(number);
        int previous = number;

        // 從小到大用質因數去整除直到超過平方根
        for (int i = 0; prime_number_of(i) <= root; i++) {
            int prime = prime_number_of(i);
            if (number % prime == 0) {
                // 遞增質因數表的數值
                int* count = (int*) table.lookup(prime.to_string()) ?? malloc0(sizeof(int));
                *count = *count + 1;
                table.replace(prime.to_string(), count);
                number = number / prime;
                break;
            }
        }

        // 如果 number 沒有變動過，number 就是質數。
        if (number == previous) {
            // 遞增質因數表的數值
            int* count = (int*) table.lookup(number.to_string()) ?? malloc0(sizeof(int));
            *count = *count + 1;
            table.replace(number.to_string(), count);
            break;
        }
    } while (number != 1);

    int result = 1;

    // 計算所有因數的個數
    foreach (int* count in table.get_values()) {
        result = result * (*count + 1);
    }

    return result;
}

// 計算平方根
int sqrt_floor_of(int num)
{
    return (int) Math.sqrt((double) num);
}

// 準備一個用來 cache 計算過的質數表
static List<int> prime_table = new List<int>();

// 質數計算
int prime_number_of(uint index)
{
    if (index < prime_table.length()) {
        // 直接從 cache 中取出
        return prime_table.nth_data(index);
    }

    // 第一個質數為 2
    if (index == 0) {
        prime_table.append(2);
        return 2;
    }
    // 第二個質數為 3
    else if (index == 1) {
        prime_table.append(3);
        return 3;
    }
    // 第三個後的質數計算
    else {
        int candidate = prime_table.nth_data(prime_table.length() - 1) + 2;
        do {
            bool is_prime = true;
            foreach (int number in prime_table) {
                if (candidate % number == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                prime_table.append(candidate);
                return candidate;
            }
            candidate = candidate + 2;
        } while (true);
    }
}

將以上程式碼儲存成 p12.vala 或是直接從 gist: 1182715 下載 然後編譯執行

$ valac p12.vala -X -lm && ./p12
Answer: 76576500
2^2*3^2*5^3*7*11*13*17=76576500