您现在的位置:首页 > >

Java面试知识点(九十三)高效判断一个数,是不是素数

发布时间:

面试的时候,如果要手写算法题目,判断一个数是不是素数,可以说是非常常见的问题了,这道题目回答并不算难,但是想要以优雅高效的方法回答,却并不轻松,下面我会介绍三种方式,时间复杂度从高到低。


注意:0和1既不是素数也不是合数


第一种方式

1.方式:从2遍历到n-1


2.时间复杂度:O(n)


3.代码示例


boolean firstMethod(int n) {
if (n < 2) {
return false;
} else if (n == 2) {
return true;
} else {
for (int i = 2; i < n; i++) {
if (n%i == 0) {
return false;
}
}
return true;
}
}

评价:最简单粗暴的方式。



第二种方式

因为,一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于 sqrt (n),一个大于等于 sqrt (n)。第二种方式就是根据这种方式


1.方式:从2遍历到sqrt(n)


2.时间复杂度:O(sqrt(n))


3.代码示例


boolean secondMethod(int n) {
if (n < 2) {
return false;
} else if (n == 2) {
return true;
} else {
// 注意这里需要强转,sqrt函数返回的是double类型的数据。
int temp = (int) Math.sqrt(n);
for (int i = 2; i <= temp; i++) {
if (n%i == 0) {
return false;
}
}
return true;
}
}

评价:初步优化,效率提升。



第三种方式

质数分布的规律:大于等于 5 的质数一定和 6 的倍数相邻。例如 5 和 7,11 和 13,17 和 19 等等;


证明:令 x≥1,将大于等于 5 的自然数表示如下:
?????? 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ??????
可以看到,不在 6 的倍数两侧,即 6x 两侧的数为 6x+2,6x+3,6x+4,由于 2 (3x+1),3 (2x+1),2 (3x+2),所以它们一定不是素数,再除去 6x 本身,显然,素数要出现只可能出现在 6x 的相邻两侧。


所以循环的步长可以设为 6,然后每次只判断 6 两侧的数即可。


/**
* 当素数大于等于5之后,一定只出现在6的倍数左右相邻两侧
* 素数一定在两侧
* 但是两侧的不一定是素数
* */
boolean thirdMethod(int n) {
// 小于5的素数只有2和3
if (n < 5) {
if (n==2 || n==3) {
return true;
} else {
return false;
}
}
// 如果该数不在6的两侧,则一定不是素数
if (n % 6 != 1 && n%6 != 5) {
return false;
}
int temp = (int)Math.sqrt(n);
// 循环步长为6,每次判断i和i+2
for (int i=5; i<=temp; i+=6) {
if (n%i == 0 || n%(i+2)==0) {
return false;
}
}
return true;
}


热文推荐
猜你喜欢
友情链接: 团党工作范文 工作范文 表格模版 社科文档网 营销文档资料 工程文档大全