質數概念
質數，又稱素數，指在一個大于1的自然數中，除了1和此整數自身外，無法被其他自然數整除的數（也可定義為只有1和本身兩個因數的數）。
最小的素數是2，也是素數中唯一的偶數；其他素數都是奇數。質數有無限多個，所以不存在最大的質數。
一：根據定義去求解：
也是最笨的方式，效率比較低：
|
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
32
|
package test.ms;public class FindPrime { // find the prime between 1 to 1000; public static void main(String[] args) { printPrime(1000); } public static void printPrime(int n){ for(int i = 2; i < n ; i++){ int count = 0; for(int j = 2 ; j<=i; j++){ if(i%j==0){ count++; } if(j==i & count == 1){ System.out.print(i+" "); } if(count > 1){ break; } } } }} |
2：平方根：
|
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
|
package test.ms;public class Prime { public static void main(String[] args) { for(int j = 2; j<1000; j++){ if(m(j)){ System.out.print(j+" "); } } } public static boolean m(int num){ for(int j = 2; j<=Math.sqrt(num);j++){ if(num%j == 0){ return false; } } return true; }} |
3：找規律（摘自一個論壇討論）
最小的素數是2，也是素數中唯一的偶數；其他素數都是奇數。質數有無限多個，所以不存在最大的質數。
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
package test.ms;import java.util.ArrayList;import java.util.List;public class Primes { public static void main(String[] args) { // 求素數 List<Integer> primes = getPrimes(1000); // 輸出結果 for (int i = 0; i < primes.size(); i++) { Integer prime = primes.get(i); System.out.printf("%8d", prime); if (i % 10 == 9) { System.out.println(); } } } /** * 求 n 以內的所有素數 * * @param n 范圍 * * @return n 以內的所有素數 */ private static List<Integer> getPrimes(int n) { List<Integer> result = new ArrayList<Integer>(); result.add(2); for (int i = 3; i <= n; i += 2) { if (!divisible(i, result)) { result.add(i); } } return result; } /** * 判斷 n 是否能被整除 * * @param n 要判斷的數字 * @param primes 包含素數的列表 * * @return 如果 n 能被 primes 中任何一個整除，則返回 true。 */ private static boolean divisible(int n, List<Integer> primes) { for (Integer prime : primes) { if (n % prime == 0) { return true; } } return false; } } |
第一種和第二種都是很簡單的方法：
第三種方法說明了一個質數的特性：在所有質數中，只有2是偶數。
如果一個數能夠被它之前的質數整除，那么這個數不是質數。
