JAVA求素数算法实现

尽管求素数在程序设计里面是基础的基础,但是对于一些初学者来说还是很难,而这类问题不管是面向对象语言还是面向过程语言的实现方法大至都是相同的,我这里写了JAVA语言的实现,供参考。
一般的求素数算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Prime {
 
	/**
	 * 一般求素数方法
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		for (int i = 2; i < 100; i++) {
			int j;
			for (j = 2; j < (int) (Math.sqrt(i) + 1); j++)
 
			{
				if (i % j == 0) {
					break;
				}
			}
 
			if (j > (int) Math.sqrt(i)) {
				System.out.print(i + " ");
			}
		}
 
	}
 
}

筛法求素数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Prime2 {
 
	/**
	 * 筛法求素数
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 100;
		int[] array = new int[n];
		for (int i = 2; i < n; i++)
			array[i] = i;
		for (int i = 2; i < n; i++) {
			if (array[i] != 0) {
				int j, temp;
				temp = array[i];
				for (j = 2 * temp; j < n; j = j + temp) {
					array[j] = 0;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if (array[i] != 0) {
				System.out.print(i + " ");
			}
		}
 
	}
 
}

-EOF-