java求质数

这两天JE求质数的帖子火了好几个哈

先介绍下质数的解释：
就是在所有比1大的整数中，除了1和它本身以外，不再有别的约数，这种整数叫做质数，质数又叫做素数。

质数判断技巧：
先找一个数m，使m的平方大于n，再用<=m的质数去除n（n即为被除数），如果都不能整除，则n必然是质数。

贴代码：

public static void main(String args[]){
		long start = System.currentTimeMillis();
// 走质数判断技巧的过程
		List<Integer> list = new ArrayList<Integer>();
		list.add(2);
		for(int i=3; i<500000 ; i+=2){
			if(isPrime(i, list)){
				list.add(i);
			}
		}
		for(int x : list){
			System.out.print(x+",");
		}
// 递归
		for(int i=3; i<500000; i+=2){
			boolean boo = true;
			for(int j=2; j<i; j++){
				if(i%j == 0){
					boo = false;
					break;
				}
			}
			if(boo){
				System.out.print(i+",");
			}
		}
// 开平方，求余
		for(int i=3; i<500000; i+=2){
			if(offPrime(i)){
				System.out.print(i+",");
			}
		}
		long end = System.currentTimeMillis();
		System.out.println();
		System.out.println(end - start);
	}

public static boolean isPrime(int i, List<Integer> ii){
		for(int j : ii){
			if(j*j <= i){
				if(i%j == 0){
					return false;
				}
			}else{
				return true;
			}
		}
		return true;
	}

public static boolean offPrime(int n){
		for(int i=3; i*i <= n; i++){
			if(n%i==0){
				return false;
			}
		}
		return true;
	}

效率不说了，mark一下