Java实现求小于n的质数的3种方法

时间:2021-12-19 14:42:47

质数概念

质数,又称素数,指在一个大于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是偶数。
如果一个数能够被它之前的质数整除,那么这个数不是质数。