Skip to content

Instantly share code, notes, and snippets.

@fourdollars
Created August 31, 2011 02:58
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save fourdollars/1182715 to your computer and use it in GitHub Desktop.
Project Euler - Problem 12
/**
* 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