package cn.edut.test_algorithm;

/** * 判断是否为素数 * 素数定义：质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。 * * Note:2也是素数，因为除了1和它本身以外不再有其他因数 * @author Administrator * */
public class Demo_isPrimeNumber {
	public static void main(String[] args) {
		for(int i=1 ; i<30 ; i++) {
			boolean flag = isPrimeNumber(i);
			if(flag)
			System.out.println(i+":"+flag);
		}
		
		System.out.println("-----------------------");
		for(int i=1 ; i<30 ; i++) {
			boolean flag = isPrimeNumber2(i);
			if(flag)
			System.out.println(i+":"+flag);
		}
	}
	
	/** * O(sqrt(n)) * （新）算法思想： * 可以证明，该程序不需要试探任何大于n的平方根的因子。 * 当n能被某一个整数d1整除时，那么就肯定还有另一个数d2能被它整除， * 即n=d1*d2,如果其中一个大于n的平方根，另一个一定小于n的平方根。 * 因此如果n有任何因子，肯定有一个小于或等于n的平方根。 * 这就意味着程序中的for循环的次数i<=根号n */
	public static boolean isPrimeNumber2(long x ) {
		if(x<2) return false ; //素数小于1
		if(x>2) {  //
			if(x%2==0) return false ; //偶数肯定不是素数
			int len = (int) Math.sqrt(x) ; 
			for(long i=2 ; i< len ; i++) {
				if(x%i==0) {
					return false ;
				}
			}
		}
		return true;
	}
	
	/** * O(N) * @param x * @return */
	public static boolean isPrimeNumber(long x ) {
		if(x<2) return false ;
		if(x>2) {
			for(long i=2 ; i<x ; i++) {
				if(x%i==0) {
					return false ;
				}
			}
		}
		return true;
	}
}