Java面试知识点（九十三）高效判断一个数，是不是素数

Myth丶恋晨 2021-09-20 23:10 427阅读 0赞

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

**注意：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;
        }