求单纯质因数的合数

PurePrime.java

package com.github.winse;

import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;

/**
 * 
 * 单纯质因数的合数
 * 
 * 具有互不相同的质因素的合数
 * 
 * XXX 除以double质数，才是正道！
 */
public class PurePrime {

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		int data = 100000;

		System.out.println("获取 " + data + " 的纯质合数: ");
		System.out.println();

		new PurePrime().printPure(data);

		long end = System.currentTimeMillis();
		System.out.println();
		System.out.println("整个过程耗时： " + (end - start) + " milliseconds");
	}

	private int count = 0;

	private void print(Object data, boolean reset) {
		System.out.print(data);
		if (reset) {
			count = 0;
		}
	}

	private void print(Object data) {
		print(data, false);
	}

	private void print(int data) {
		if (count > 0 && (count % 20 == 0)) {
			System.out.println();
		}
		count++;
		print(data + "\t");
	}

	private List<Case> latestLevelPure;

	public void printPure(int data) {
		Integer[] primes = getPrime(data);
		System.out.println("符合要求的质数有： " + Arrays.toString(primes));

		BitSet pureData = new BitSet(data);
		// 理论上组合的因子个数
		int combination = 1;
		while (combination <= primes.length) {
			List<Case> results = fixNumArgs(data, primes, combination);
			if (results != null)
				for (Case cs : results) {
					pureData.set(cs.value());
				}
			combination++;
		}

		for (int i = 0; i < data; i++) {
			if (pureData.get(i)) {
				print(i);
			}
		}
	}

	private List<Case> fixNumArgs(int data, Integer[] primes, int combination) {
		List<Case> latestCases;
		// 因子个数(M)在(M-1)个因子的基础上进行进行
		if (combination == 1) {
			latestCases = new LinkedList<Case>();
			for (int i = 0; i < primes.length; i++) {
				latestCases.add(new Case(primes[i], i));
			}
		} else {
			latestCases = latestLevelPure;
		}

		if (latestCases == null || latestCases.size() == 0) {
			return null;
		}

		List<Case> newCases = new LinkedList<>();
		for (Case cs : latestCases) {
			int index = cs.index() + 1;
			for (; index < primes.length; index++) {
				int np = primes[index];
				int m = cs.multi(np);
				if (m > 0 && m < data) {
					Case newCase = cs.clone2();
					newCase.add(np, index);
					newCases.add(newCase);
				} else {
					break;
				}
			}
		}

		System.out.println(combination + " : size$" + String.valueOf(newCases.size()) + "=> "
				+ (newCases.size() > 100 ? "" : Arrays.toString(newCases.toArray())));
		return latestLevelPure = newCases;
	}

	static class Case implements Cloneable {
		private int value = 1;
		// 在质数列表中的位置，数字从零开始
		private int index;

		public Case(int data, int index) {
			value *= data;
			this.index = index;
		}

		public Case clone2() {
			try {
				return (Case) this.clone();
			} catch (CloneNotSupportedException e) {
				throw new RuntimeException(e);
			}
		}

		@Override
		public Object clone() throws CloneNotSupportedException {
			return super.clone();
		}

		@Override
		public String toString() {
			return value + "[" + index + "]";
		}

		public Case add(int data, int index) {
			value *= data;
			this.index = index;
			return this;
		}

		public int index() {
			return this.index;
		}

		public int multi(int data) {
			return this.value * data;
		}

		public int value() {
			return value;
		}

	}

	/**
	 * @see <a href="http://liugang594.iteye.com/blog/753399">求质数的方法</a>
	 */
	private Integer[] getPrime(int data) {
		long start = System.currentTimeMillis();

		List<Integer> list = new LinkedList<Integer>();

		// TODO 可以考虑只存奇数
		BitSet b = new BitSet(data + 1);// 用于记录是否为质数

		int i;
		for (i = 2; i <= data; i++) {
			b.set(i); // 初始化
		}

		// 忽略 1
		i = 2;
		while (i * i <= data) {
			if (b.get(i)) {
				list.add(i);

				// 清除所有i的倍数, 2i/3i/...
				int k = 2 * i;
				while (k <= data) {
					b.clear(k);
					k += i;
				}
			}
			i++;
		}

		// 处理剩余没处理的
		while (i <= data) {
			if (b.get(i))
				list.add(i);
			i++;
		}
		long end = System.currentTimeMillis();
		System.out.println("获取质数用时： " + (end - start) + " milliseconds");

		return list.toArray(new Integer[0]);
	}

}