2013年8月10日土曜日

Math Toolの素因数分解コード

Androidアプリ Math Tool ( https://play.google.com/store/apps/details?id=jp.blogspot.tsukinihinikeni.mathtool )で使用している素因数分解のコードです。

エラー処理、バックグラウンドプロセスに関する処理など、直接素因数分解に関係ない部分は省略しています。



TextView tv = (TextView) findViewById(R.id.***);
BigInteger n = new BigInteger(***);

if (n.abs().equals(BigInteger.ZERO)) {
tv.setText("0 = 0");
} else if (n.equals(BigInteger.ONE)) {
tv.setText("1 = 1");
} else if (n.negate().equals(BigInteger.ONE)) {
tv.setText("-1 = -1");
} else {
String factor = factorize(n);

String txt = "";
txt += n.toString() + " = ";
txt += factor;
tv.setText(txt);
}


private String factorize(BigInteger n) {

String f = "";
int factor_count = 0;

if (n.signum() == -1) {
f = "-1 * ";
n = n.negate();
}

ArrayList<String> factor_str = new ArrayList<String>();
ArrayList<Integer> index = new ArrayList<Integer>();

//primesは素数が小さい順に入っている配列(素数リスト)
//p_max_orderは素数リストの要素数
//p_maxは素数リストより大きい最小の自然数

for (int i = 0; i < p_max_order; i++) {

BigInteger p = new BigInteger(primes.get(i));
if (p.pow(2).compareTo(n) == 1) {
break;
}

int k = 0;

while (n.mod(p).equals(BigInteger.ZERO)) {
k++;
n = n.divide(p);
}

if (k > 0) {
factor_count++;
factor_str.add(p.toString());
index.add(k);
}
}

if (!n.equals(BigInteger.ONE)) {
factor_count++;
factor_str.add(n.toString());
index.add(1);
}

String notation = "";
if (n.compareTo((new BigInteger(p_max)).pow(2)) >= 0) {
notation = "\n  # " + n.toString() + " は " + p_max
+ " 以上の素数で割り切れる可能性があります.";
} else if (factor_count == 1 && index.get(0) == 1 && f == "") {
notation = " (素数)";
}

for (int i = 0; i < factor_count; i++) {
if (i > 0) {
f += " * ";
}

if (index.get(i) == 1) {
f += factor_str.get(i);
} else {
f += factor_str.get(i) + "^" + index.get(i);
}
}

f += notation;

return f;
}




アプリの使い方などは
http://tsukinihinikeni.blogspot.jp/2013/08/math-toolandroid.html
をご覧ください。

素数のリストについては、Excelで作成したCSVでアプリ内に保持しています。
作成方法は
http://tsukinihinikeni.blogspot.jp/2012/01/blog-post.html
をご覧ください。

0 件のコメント:

コメントを投稿