Project Euler - Problem 12
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Copyright (C) 2011 Shih-Yuan Lee (FourDollars) <fourdollars@gmail.com> | |
* | |
* This program is free software: you can redistribute it and/or modify | |
* it under the terms of the GNU General Public License as published by | |
* the Free Software Foundation, either version 3 of the License, or | |
* (at your option) any later version. | |
* | |
* This program is distributed in the hope that it will be useful, | |
* but WITHOUT ANY WARRANTY; without even the implied warranty of | |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
* GNU General Public License for more details. | |
* | |
* You should have received a copy of the GNU General Public License | |
* along with this program. If not, see <http://www.gnu.org/licenses/>. | |
*/ | |
void main() | |
{ | |
int i = 0, number = 0; | |
// 用來儲存質數分解的結果 | |
HashTable<int, 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<int, int> factors) | |
{ | |
int number = 1; | |
List<int> keys = factors.get_keys(); | |
// 把質因數表的鍵值依照數值大小重新排序 | |
keys.sort( (a, b) => { | |
int num1 = a; | |
int num2 = b; | |
if (num1 < num2 ) { | |
return -1; | |
} | |
else if (num1 > num2) { | |
return 1; | |
} | |
else { | |
return 0; | |
} | |
}); | |
// 驗算過程 | |
foreach (int key in keys) { | |
int count = factors.lookup(key); | |
int prime = 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; | |
} | |
} | |
stdout.printf("\b=%d\n", number); | |
} | |
// 三角數的計算 | |
int triangle_number(int num) | |
{ | |
return num * (num + 1) / 2; | |
} | |
// 找出某數值的質因數分解 | |
int factor_number_of(int number, out HashTable<int, int> table) | |
{ | |
table = new HashTable<int, int>(direct_hash, direct_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 = table.lookup(prime); | |
table.replace(prime, count + 1); | |
number = number / prime; | |
break; | |
} | |
} | |
// 如果 number 沒有變動過,number 就是質數。 | |
if (number == previous) { | |
// 遞增質因數表的數值 | |
int count = table.lookup(number); | |
table.replace(number, count + 1); | |
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); | |
} | |
} | |
/* -*- coding: utf-8; indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*- */ | |
/* vim:set fileencodings=utf-8 tabstop=4 expandtab shiftwidth=4 softtabstop=4: */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment