算法求素数_JAVA_程序员俱乐部

您所在的位置：程序员俱乐部 > 编程开发 > JAVA > 算法求素数

算法求素数

2014/4/3 18:27:39 tanjw 程序员俱乐部我要评论(0)

摘要：这里我写了几个求素数的方法和大家交流一下//①进行穷举时间复杂度O(n)privatestaticbooleanprimer1(intnumber){for(inti=2;i<number-1;i++){if(number%i==0){returnfalse;}}returntrue;}//②使用√n进行计算时间复杂度O(√n)privatestaticbooleanprimer2(intnumber){//这里我们使用i*i而不使用Math.sqrt(number
标签：算法

这里我写了几个求素数的方法和大家交流一下

// ① 进行穷举时间复杂度O(n)

class="java">	private static boolean primer1(int number) {
		for(int i = 2 ; i < number -1 ; i++ ){
			if(number%i == 0){
				return false ;
			}
		}
		return true;
	}

?// ② 使用 √n 进行计算时间复杂度O(√n)

	private static boolean primer2(int number) {
		// 这里我们使用 i*i 而不使用 Math.sqrt(number) 因为求根是一个非常耗时的操作
		for (int i = 2; i*i<number; i++) { 
			if(number%i == 0){
				return false ;
			}
		}
		return true;
	}

? // ③ 使用爱拉托逊斯算法充分利用了一素数的定义如果一个数 m 是另一个数 n 的倍数则这个数肯定不是素数时间复杂度

?
?

	private static boolean primer3(int number) {
		boolean[] prime = new boolean[number];  
		for (int i = 2; i < prime.length - 1; i++) {
			if(!prime[i-1])
				for (int j = i - 1; j < prime.length; j += i) 
					prime[j] = true ;
		}
		return !prime[number-1];
	}