Project Euler #016

/**
 * Copyright hycro ( http://wonderfl.net/user/hycro )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/slqY
 */

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	
	public class ProjectEuler extends Sprite {
		private var _textField:TextField;
		
		public function ProjectEuler() {
			initialize();
			writeAnswer(new Problem016);
		}
		
		private function writeAnswer(problem:AbstructProblem):void {
			var answer:String = problem.getAnswer();
			_textField.appendText(answer);
		}
		
		private function initialize():void {
			_textField = new TextField();
			_textField.width = stage.stageWidth;
			_textField.height = stage.stageHeight;
			addChild(_textField);
			_textField.wordWrap = true;
		}
	}
}

class AbstructProblem {
	final public function getAnswer():String {
		var answer:String;
		try {
			answer = solve().toString();
		} catch (err:Error) {
			answer = err.getStackTrace();
		}
		return answer;
	}
	
	protected function solve():Number {
		throw new Error("unsolved");
	}
}

class Problem016 extends AbstructProblem {
	override protected function solve() : Number {
		var answer:Number;
		
		// 2^1000 を計算
		var bigInt:SimpleBigInteger = new SimpleBigInteger();
		for (var i:uint = 0; i < 1000; i++) {
			bigInt.multiple(2);
		}
		
		// 2^1000 の各桁の総和を求める
		var sequence:Vector.<uint> = bigInt.digits;
		answer = 0;
		for each (var n:uint in sequence) {
			answer += n;
		}
		
		return answer;
	}
}

class SimpleBigInteger {
	private var _digits:Vector.<uint>;
	
	public function SimpleBigInteger() {
		_digits = new Vector.<uint>();
		_digits[0] = 1;
	}
	
	public function multiple(n:uint):void {
		var carry:uint = 0;
		for (var i:uint=0; i<_digits.length; i++) {
			var prevCarry:uint = carry;
			carry = (_digits[i] * n + carry) / 10;
			_digits[i] = (_digits[i] * n + prevCarry) % 10;
		}
		for (var j:uint=1; j <= MathUtil.digits(carry); j++) {
			_digits[i + j - 1] = MathUtil.numberAt(carry, j);
		}
	}
	
	public function get digits():Vector.<uint> {
		return _digits;
	}
}

class MathUtil {
	// 整数値の桁数の取得
	static public function digits(n:Number, radix:uint=10):Number {
		var d:Number = 0;
		
		n = Math.abs(n);
		while (n / radix != 0) {
			n = Math.floor(n / radix);
			d++;
		}
		
		return d;
	}
	
	// 指定した桁の値を取得
	static public function numberAt(n:Number, digit:Number, radix:Number=10):Number {
		var number:Number;
		
		while (--digit) {
			n = Math.floor(n / radix);
		}
		
		return n % radix
	}
	
	// 素因数分解
	static public function primeFactorization(n:Number):Vector.<Number> {
		var prime:Number = 2;
		var sequence:Vector.<Number> = new Vector.<Number>();
		
		while (n != 1) {
			while (n % prime != 0) {
				prime++;
			}
			sequence.push(prime);
			n /= prime;
		}
		return sequence;
	}
	
	// 素数を列挙
	static public function getPrimeList(limit:uint):Vector.<uint> {
		var sequence:Vector.<uint> = new Vector.<uint>(limit);
		
		for (var i:uint = 2; i < limit; i++) {
			sequence[i] = i;
		}
		
		for (i=2; i < limit; i++) {
			if (sequence[i]) {
				for (var j:uint = i+i; j < limit; j+=i) {
					sequence[j] = 0;
				}
			}
		}
		
		var primeList:Vector.<uint> = new Vector.<uint>();
		for (i=2; i < limit; i++) {
			if (sequence[i]) {
				primeList.push(i);
			}
		}
		
		return primeList;
	}
	
	
	// 約数の数を取得
	static public function countFactor(n:uint):uint {
		var primes:Vector.<Number> = MathUtil.primeFactorization(n);
		var counts:Vector.<uint> = new Vector.<uint>();
		
		var prev:Number = 0;
		for each(var prime:Number in primes) {
			if (prime == prev) {
				counts[counts.length-1]++;
			} else {
				counts[counts.length] = 1;
				prev = prime;
			}
		}
		
		var count:uint = 1;
		for each (var n:uint in counts) {
			count *= n + 1;
		}
		
		return count;
	}
	
	// 組み合わせの計算
	static public function collection(n:uint, m:uint):Number {
		var length:uint = n - m + 1;
		var ans:Fraction = new Fraction(1, 1);
			
		for (var i:int=n; i>= length; i--) {
			ans = ans.multiple(new Fraction(i, i - m));
		}
			
		return ans.toNumber();
	}

}

/**
 * 分数クラス
 */
class Fraction {
	// 分子
	private var _numerator:Number;
	// 分母
	private var _denominator:Number;
	
	/**
	 * コンストラクタ
	 * 
	 * @param n 分子
	 * @param d 分母
	 */
	public function Fraction(n:Number, d:Number) {
		_numerator = n;
		_denominator = d;
	}
	
	/**
	 * 加算します
	 * 
	 * @param f 被演算子
	 * @return 加算結果
	 */
	public function add(f:Fraction):Fraction {
		return new Fraction(_numerator * f.denominator + f.numerator * _denominator, _denominator * f.denominator).reduce();
	}
	
	/**
	 * 減算します
	 * 
	 * @param f 被演算子
	 * @return 減算結果
	 */
	public function subtruct(f:Fraction):Fraction {
		return new Fraction(_numerator * f.denominator - f.numerator * _denominator, _denominator * f.denominator).reduce();
	}
	
	/**
	 * 乗算します
	 * 
	 * @param f 被演算子
	 * @return 乗算結果
	 */
	public function multiple(f:Fraction):Fraction {
		return new Fraction(_numerator * f.numerator, _denominator * f.denominator).reduce();
	}
	
	/**
	 * 除算します
	 * 
	 * @param f 被演算子
	 * @return 除算結果
	 */
	public function divide(f:Fraction):Fraction {
		return new Fraction(_numerator * f.denominator, _denominator * f.numerator).reduce();
	}
	
	/**
	 * 約分します
	 * 
	 * @return 約分後の分数
	 */
	public function reduce():Fraction {
		var nPrimes:Vector.<Number> = MathUtil.primeFactorization(_numerator);
		var dPrimes:Vector.<Number> = MathUtil.primeFactorization(_denominator);
		
		for (var i:int=nPrimes.length-1; i>=0; i--) {
			for (var j:int=dPrimes.length-1; j>=0; j--) {
				if (nPrimes[i] == dPrimes[j]) {
					nPrimes.splice(i, 1);
					dPrimes.splice(j, 1);
					break;
				}
			}
		}
		
		var num1:Number = 1;
		var num2:Number = 1;
		for each (var n:Number in nPrimes) {
			num1 *= n;
		}
		for each (var d:Number in dPrimes) {
			num2 *= d;
		}
		
		return new Fraction(num1, num2);
	}
	
	/**
	 * 分子を取得します
	 * 
	 * @return 分子
	 */
	public function get numerator():Number {
		return _numerator;
	}
	
	/**
	 * 分母を取得します
	 * 
	 * @return 分母
	 */
	public function get denominator():Number {
		return _denominator;
	}
	
	/**
	 * 除算を実行してNumber型に変換します
	 * 
	 * @return 実数
	 */
	public function toNumber():Number {
		return _numerator / _denominator;
	}
	
	/**
	 * このオブジェクトの文字列表現を返します
	 * 
	 * @return "[分子]/[分母]"の形式の文字列
	 */
	public function toString():String {
		return _numerator.toString() + "/" + _denominator.toString();
	}
}