面试常备题素数的判断

明年就要开始找工作了，所以现在正在准备中，恶补一些数据结构的基础知识和面试题目，因此，在这里不定期的整理一些题目。我发现，素数判断是一个很常见的算法，基本上，我看到的很多题目都要涉及到素数的判断，比如说，1024到687432的所有素数的和，或者720的N次方中，有哪些数是素数等等，大体涉及到素数的题目，核心问题就是要懂得如何判断素数。

那么，如何判断素数呢？素数是指只能被自身和1整除的自然数，常见而且比较容易实现的算法是试除法：将该数N用<=N的所有素数去试除，若均无法整除，则N为素数。

接下来我们就开始写代码了：

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

然后我们再进行测试：

public class test{
  public static void main(String[] args){
      for(int i = 0; i < 100; i++){
         if(isPrime(i)){
           System.out.println(i + "是素数");
         }
      }
  }
}

输出结果是：

2是素数
3是素数
5是素数
7是素数
11是素数
13是素数
17是素数
19是素数
23是素数
29是素数
31是素数
37是素数
41是素数
43是素数
47是素数
53是素数
59是素数
61是素数
67是素数
71是素数
73是素数
79是素数
83是素数
89是素数
97是素数

代码并不需要背，只要知道算法，程序员就可以编写出想要的代码出来。

所以，这里我就再一次重复一下算法：只要一个数N，在[2,sqrt(N)]的区间内，没有任何数可以整除它，它就是一个素数。为什么是2呢？因为0不可能作为除数，任何数都可以除以1。

有关素数的判断还是一个小问题，就像上面讲的，需要结合具体的题目，而且，这些题目往往潜伏着陷阱，比如说，以下这道题目：

在720的N次方中，有多少个是素数？

这样的题目看似很简单，我们可以一下子就做出来：

看代码：

public class test{
      int number = 1;
      int counter = 0;
      for(int i = 0; i < Integer.MAX_VALUE; i++){
           number *= 720;
           if(isPrime(number){
              counter++;
           }
      }
      System.out.println(counter);
}

做到这里，相信大家一定看出了问题：就是我们该如何确定那个N呢？这里使用了正整数的最大值，但我们知道，一定会出错，因为这样绝对超出了整数的最大范围，确定N才是这道题目的关键：

 int getRange(int number, int divisor) {
      int range = 0;
      while ((number / divisor != 0)) {
           range++;
           number = number / divisor;
       }
      return range;
}

接着是进行测试：

public static void main(String[] args) {
      int number = 1;
      int divisor = 720;
      int range = getRange(Integer.MAX_VALUE, divisor);
      for (int i = 0; i < range; i++) {
            number *= divisor;
            if (isPrime(number)) {
                System.out.println(number + "是素数");
             }
       }

}

必须确保我们的判断数始终在java整数的范围内。

这里就卖弄一下java的整数范围：-2的31次方到2的31次方减1。