package com.ponyjava.common.util;

import java.util.HashMap;
import java.util.Map;

public class PrimeNumber {
	private static final Map<Integer, int[]> primeMap = new HashMap<Integer, int[]>();

	/**
	 * 查找下一個素數
	 * 
	 * @param max
	 *            最大的數
	 * @param pre
	 *            上一個素數
	 * @return 如果沒有下一個則返回0；如果上一個素數不在范圍內，返回-1。
	 */
	public static int getNextPrime(int max, int pre) {
		int[] primeArr = primeMap.get(max);
		if (primeArr == null) {
			primeArr = generatorPrimes(max);
			primeMap.put(max, primeArr);
		}
		return getNext(primeArr, pre);
	}

	/**
	 * 尋找下一個
	 * 
	 * @param primeArr
	 * @param pre
	 * @return
	 */
	private static int getNext(int[] primeArr, int pre) {
		for (int i = 0; i < primeArr.length; i++) {
			if (pre == primeArr[i]) {
				if (primeArr.length > i + 1) {
					return primeArr[i + 1];
				} else {
					return 0;
				}
			}
		}
		return -1;
	}

	/**
	 * 創建素數
	 * 
	 * @param max
	 * @return
	 */
	private static int[] generatorPrimes(int max) {
		int size = max + 1;
		int[] allArr = new int[size];
		// 0和1都不是素數
		allArr[0] = 1;
		allArr[1] = 1;
		// 挖空
		for (int i = 2; i < Math.sqrt(size - 1); i++) {
			if (allArr[i] == 0) {
				for (int j = 2; j <= ((size - 1) / i); j++) {
					allArr[i * j] = 1;
				}
			}
		}
		// 素數數量
		int primeCount = 0;
		for (int i = 0; i < allArr.length; i++) {
			primeCount += allArr[i];
		}
		primeCount = size - primeCount;
		// 素數數組
		int[] primeArr = new int[primeCount];
		int index = 0;
		for (int i = 0; i < allArr.length; i++) {
			if (allArr[i] == 0) {
				primeArr[index++] = i;
			}
		}
		return primeArr;
	}
}