uni/inf2440/hw2/Sequential.java

import java.util.ArrayList;

class Sequential implements Solver {
	public void solve(Sieve sieve) {
		sieve.generatePrimes();
	}

	public long[] factor(Sieve sieve, long num) {
		if (num < sieve.maxNum && sieve.isPrime((int)num))
			return new long[] { num };

		int sqrt = (int)Math.sqrt(num);

		ArrayList<Long> arr = new ArrayList<>();

		// Easier to assume all primes are odd
		while (num % 2 == 0) {
			arr.add(new Long(2));
			num /= 2;
		}

		// Find factors
		long prime;
		for (prime = 3; prime <= sqrt; prime += 2) {
			if (!sieve.isPrime((int)prime))
				continue;

			if (num % prime == 0) {
				do {
					arr.add(new Long(prime));
					num /= prime;
				} while (num % prime == 0);
				sqrt = (int)Math.sqrt(num);
			}
		}

		// Add num if we didn't find all the factors before sqrt(num)
		if (num != 1)
			arr.add(new Long(num));

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