素数的判断
素数的判断
明年就要开始找工作了，所以现在正在准备中，恶补一些数据结构的基础知识和面试题目，因此，在这里不定期的整理一些题目。我发现，素数判断是一个很常见的算法，基本上，我看到的很多题目都要涉及到素数的判断，比如说，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。
标签: java 面试题
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息