使用Java函数判断是否为素数

素数是只能被1和自身整除的正整数，如2、3、5、7等。在日常生活和计算机编程中，判断一个数是否为素数是非常常见的操作。本文将介绍使用Java函数判断一个数是否为素数的方法。

1. 常规算法

判断一个数是否为素数，最常见的方法就是暴力枚举它所有可能的因数，然后判断是否只有1和自身两个因数。具体实现如下：

public static boolean isPrime(int num) {
  if (num < 2) {
    return false;
  }
  for (int i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

首先判断num是否小于2，因为2是最小的素数。然后从2开始到num的平方根循环遍历，如果num能被循环变量i整除，则num不是素数。最后如果循环结束仍未返回false，则num是素数。

2. 优化算法

对于大数而言，暴力算法有很明显的缺陷：枚举倍数的时间复杂度为O(n)，效率很低。相比之下，更快的方法是使用筛法求素数。筛法的基本思路是先将所有的数标记为合数，然后从2开始遍历，将不是合数的数标记为素数。具体实现如下：

public static boolean isPrime(int num) {
  if (num < 2) {
    return false;
  }
  boolean[] prime = new boolean[num + 1];
  Arrays.fill(prime, true);
  for (int i = 2; i * i <= num; i++) {
    if (prime[i]) {
      for (int j = i * i; j <= num; j += i) {
         prime[j] = false;
      }
    }
  }
  return prime[num];
}

首先判断num是否小于2，然后创建一个boolean类型的数组prime，用于标记所有的数字是否为素数。将数组的所有值初始化为true，然后从2开始遍历到num的平方根。如果当前的数是素数，则将它的所有倍数都标记为合数。最后如果num为素数，则返回true。这种算法的时间复杂度为O(nloglogn)，比暴力算法高效很多。

3. 多线程算法

对于非常大的数，使用单线程算法的速度仍然很慢，因为需要判断的数非常多。有一种优化方法是使用多线程算法，将所有的数分为若干批次，每个线程处理一批数字。具体实现如下：

public static boolean isPrime(int num, int threadNum) {
  if (num < 2) {
    return false;
  }
  int batch = num / threadNum;
  int remaining = num % threadNum;
  boolean[] prime = new boolean[num + 1];
  Arrays.fill(prime, true);
  PrimeThread[] threads = new PrimeThread[threadNum];
  for (int i = 0; i < threadNum; i++) {
    int start = i * batch;
    int end = (i + 1) * batch - 1;
    if (i == threadNum - 1) {
      end += remaining;
    }
    threads[i] = new PrimeThread(start, end, prime);
    threads[i].start();
  }
  try {
    for (int i = 0; i < threadNum; i++) {
      threads[i].join();
    }
  } catch (InterruptedException e) {
    e.printStackTrace();
  }
  return prime[num];
}

private static class PrimeThread extends Thread {
  private int start;
  private int end;
  private boolean[] prime;

  public PrimeThread(int start, int end, boolean[] prime) {
    this.start = start;
    this.end = end;
    this.prime = prime;
  }

  public void run() {
    for (int i = 2; i * i <= end; i++) {
      if (prime[i]) {
        int j = Math.max(i * i, ((start + i - 1) / i) * i);
        for (; j <= end; j += i) {
          prime[j] = false;
        }
      }
    }
  }
}

首先判断num是否小于2，然后将所有的数字分为threadNum批次，每个线程处理一批数字。创建一个boolean类型的数组prime，用于标记所有的数字是否为素数。将数组的所有值初始化为true。创建threadNum个线程，并让它们开始处理数字。每个线程的处理逻辑与优化算法类似，只是要处理的数字范围不同。最后等待所有线程都处理完毕，然后返回num是否为素数。这种算法的时间复杂度随线程数的增加而下降。

总的来说，判断一个数是否为素数是一项非常基础的操作。本文介绍了三种方法：常规算法、优化算法和多线程算法。在实际项目中，应该选择合适的算法来处理具体问题。