TopCoder SRM 643 Div1 Easy: TheKingsFactorization (素因数分解)

問題

TopCoder Statistics - Problem Statement

解法

上のような整数を素因数分解する場合、ヒントを駆使しても10の8乗ループをすることになるが、primes[i] <= N/primes[i+1] <= primes[i+1]ならば、N/primes[i+1]は必ず素数で、primes[i]とprimes[i+1]の間にあるので、ループする必要がなくなる。

コード

import java.util.ArrayList;

public class TheKingsFactorization {

	public long[] getVector(long N, long[] primes) {
		ArrayList<Long> ans = new ArrayList<>();
		for (int i = 0; i < primes.length; i++) {
			N /= primes[i];
			ans.add(primes[i]);

			if (i < primes.length - 1 && primes[i] == primes[i + 1]) {
				// primes[i]=primes[i+1]ならば、その間にある素数もprimes[i]である
				N /= primes[i];
				ans.add(primes[i]);
				continue;
			}

			if (i == primes.length - 1) {
				// 最後の素数で割り終わってもNが1になっていない時、残ったNは必ず素数である
				if (N != 1) {
					ans.add(N);
				}
				break;
			}

			// primes[i]が2の時、Nが2で割れるかどうか
			if (primes[i] == 2) {
				if (N % 2 == 0) {
					N /= 2;
					ans.add(2L);
					continue;
				}
				primes[i]++;
			}

			if (N / primes[i + 1] <= primes[i + 1] && N > primes[i + 1]) {
				// N / primes[i + 1] <= primes[i + 1]ならば、
				// 素数列はprimes[i], N/primes[i+1], primes[i+1]という並びになる
				ans.add((long) N / primes[i + 1]);
				N = primes[i + 1];
				continue;
			}

			for (long j = primes[i]; j <= Math.min(primes[i + 1], Math.min(Math.sqrt(N), N / primes[i + 1])); j += 2) {
				if (N % j == 0) {
					N /= j;
					ans.add(j);
					break;
				}
			}

		}

		long[] ret = new long[ans.size()];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = ans.get(i);
		}

		return ret;
	}
}