面试常备题----素数的判断

面试常备题----素数的判断 恶补一些数据结构的基础知识和面试题目，因此，在这里不定期的整理一些题目。我发现，素数判断是一个很常见的算法，基本上，我看到的很多题目都要涉及到素数的判断，比如说，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 = 2; 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。