面试-编程-质数

第一种算法

 

	public static boolean prime(int num){
		for (int i = 2; i <= num/2 ; i++) {
			if(num % i == 0){
				return false;
			}
		}	
		return true;
	}

 看后不得不佩服原创多太有才了，一个整数传过来，for循环i初始值为2，第一步首先砍掉了偶数的。先发制人，一箭双雕。

第二种做法，借第一种做法。判断num=1 或者2省略

 

public static boolean prime(int num){
		int sqrtnum = (int) Math.sqrt(num);
		for (int i = 2; i <= sqrtnum ; i++) {
			if(num % i == 0){
				return false;
			}
		}	
		return true;
	}

 这种做法我还不知道为啥可以对只小于平方根的比较就知道是质数了。

测试：

 

	public static void main(String[] args) {
		for (int i = 2; i < 100; i++) {
			if (prime(i)) {
				System.out.print(" "+ i);
			}
		}
	}