Java求质数常见几种方式

1、循环遍历

1.  
   public static boolean isPrime(int num) {
2.  
   if (num <= 1) {
3.  
   return false;
4.  
   }
5.  
   // 一定是 <= 号
6.  
   for (int i = 2; i <= Math.sqrt(num); i ) {
7.  
   if (num % i == 0) {
8.  
   return false;
9.  
   }
10.  
    }
11.  
    return true;
12.  
    }

该方法的作用是判断一个整数是否是质数（即只能被1和自身整除的正整数）。方法接收一个整数参数num，返回一个布尔值，表示num是否为质数。

方法的实现原理是使用for循环从2到num的平方根（简单思考就可以想到不需要遍历到num-1）进行遍历，判断num是否能被这个数整除。如果能被整除，说明num不是一个质数，直接返回false。如果遍历完所有可能的因子都不能被整除，说明num是一个质数，返回true。

需要注意的是，该方法对于num小于等于1的情况直接返回false，因为1不是质数。

这种方法的时间复杂度为 O(n*sqrt(n)) ，在n的值很大的时候效率较低，如果需要找出大量质数，可以用更高效的算法，另外常见的两种方法为埃氏筛法和欧拉筛法

2、埃氏筛法（埃拉托斯特尼筛法）

埃氏筛法是一种简单又历史悠久的筛法。

埃氏筛法的基本思路是先把从2开始的所有数写下来，然后从2开始，将每个质数的倍数都标记成合数，即非质数，直到筛完所有小于等于给定数n的数。这样，留下的就是小于等于n的质数。

1.  
   public static List<Integer> getPrimes(int n) {
2.  
    
3.  
   // 为了下标和n对应，数组长度为n 1
4.  
   boolean[] isComposite = new boolean[n 1]; // 标记数组，false表示该下标对应的数是质数
5.  
   List<Integer> primes = new ArrayList<>(); // 用动态数组ArrayList存储质数
6.  
    
7.  
   for (int i = 2; i <= n; i ) {
8.  
   if (!isComposite[i]) { // 如果该数是质数
9.  
   primes.add(i); // 把该数加入质数列表
10.  
    /* 常规思路是从 i * 2 开始，但是这样会重复判断多次
11.  
    从 i * i 开始遍历，可以略过很多次判断，因为只有
12.  
    从i的平方开始才不会和前面重复，略过了与前面数字
13.  
    的公倍数
14.  
    例如i = 2时，从4开始，判断 4 6 8 10 12 14...
15.  
    当i=3时，只需要从9开始判断3的倍数，而不需要判断
16.  
    2和3的公倍数6
17.  
    */
18.  
    for (int j = i * i; j <= n; j = i) { // 标记该数的倍数为合数
19.  
    isComposite[j] = true;
20.  
    }
21.  
    }
22.  
    }
23.  
     
24.  
    return primes;
25.  
    }

埃氏筛法时间复杂度为O(nloglogn)， 此算法会重复筛，如i=2时已经判断过12，但i=3时仍然需要再次判断，增加了时间复杂度，此算法依然有优化的空间

3、欧拉筛法

欧拉筛法的基本思路是将每个数表示为质数的乘积，然后按照质数的倍数依次筛选，这样每个合数只会被筛选一次，大大减少了时间复杂度

1.  
   public static List<Integer> eulerSieve(int n) {
2.  
    
3.  
   boolean[] isPrime = new boolean[n 1]; // 标记数组，false表示该下标对应的数是质数
4.  
   List<Integer> primes = new ArrayList<>(); // 用动态数组ArrayList存储质数
5.  
   for (int i = 2; i <= n; i ) {
6.  
   if (!isPrime[i]) { // 如果该数是质数
7.  
   primes.add(i); // 就放入数组中
8.  
   }
9.  
   // 循环质数的个数次 并且不能超出范围
10.  
    for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j ) {
11.  
    // i的倍数一定是合数
12.  
    isPrime[i * primes.get(j)] = true;
13.  
    // 关键 当i能整除的时候就跳出循环
14.  
    if (i % primes.get(j) == 0) {
15.  
    break;
16.  
    }
17.  
    }
18.  
    }
19.  
    // primes列表中存储的就是所有小于等于n的质数
20.  
    return primes;
21.  
    }

 欧拉筛法的时间复杂度是O(n)，每一个合数都被它的最小质因数筛掉

这篇好文章是转载于：学新通技术网