判断一个数是否是素数

深碍√TFBOYSˉ_ 2023-07-17 15:41 19阅读 0赞

### 什么是素数？ ###

素数释义：

曾称*质数*。一个大于1的正整数，如果除了1和它本身以外，不能被其他正整数整除，就叫*素数*。如2，3，5，7，11，13，17…。

### 根据素数定义判断素数 ###

public boolean isPrime(int n){
        if(n < 4){
            return n>1;
        }
        for(int i=2;i<n;i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }

从2开始，一直到小于其自身，依次判断能否被n整除即可，能够整除则不是质数，否则是质数。

### 初步优化 ###

参考**算法**一书，人民邮电出版社

假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)

public boolean isPrime(int n) {
        if (n <= 3) {
            return n > 1;
        }
        int sqrt = (int)Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }

### 最终优化 ###

质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

**6x能被2,3,6整除肯定不是质数**

**6x+1**

**6x+2 能被2整除**

**6x+3 能被3 整除**

**6x+4 能被2整除**

**6x+5 等价于6x-1**

public static boolean isPrime(int num) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java：判断一个整数是否是素数

素数：除了1和它本身不能被任何一个数整除。判断某个是是否是素数，只要判断某个数m是否能被2到Math.sqrt(m)整除。 package choi; imp

超、凢脫俗/ 2024年03月25日 22:17/ 0 赞/ 90 阅读

相关判断一个数是否是素数

什么是素数？素数释义：曾称质数。一个大于1的正整数，如果除了1和它本身以外，不能被其他正整数整除，就叫素数。如2，3，5，7，11，13，17…。根据素数定义

深碍√TFBOYSˉ_/ 2023年07月17日 15:41/ 0 赞/ 20 阅读

相关判断一个数是否为素数

判断一个数是否为质数：质数是指大于1的自然数中除1与自身外没有其他因数 include<iostream> using namespace std;

àì夳堔傛蜴生んèń/ 2023年06月15日 13:24/ 0 赞/ 34 阅读

相关 JAVA实现判断键盘输入一个数是否是素数

判断键盘输入一个数是否是素数 > 素数：只能被1和它本身整除代码 int i,n; Scanner scan = new Sca

Love The Way You Lie/ 2023年03月01日 10:07/ 0 赞/ 15 阅读

相关快速判断一个数字是否是素数

//num可以达到10^9数量级甚至更大，比一般的判断方法快很多 </pre><pre name="code" class="cpp">bool isPrim

浅浅的花香味﹌/ 2022年08月04日 04:07/ 0 赞/ 235 阅读

相关 C语言判断一个数是否为素数

素数又称质数。所谓素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2~16的任一整数整除。思路1)：因此判断一个整数m是否是素数，

╰+哭是因爲堅強的太久メ/ 2022年06月14日 01:50/ 0 赞/ 309 阅读

相关怎么判断一个数是否是素数

package mytest; import java.util.Scanner; public class test { publ

墨蓝/ 2022年05月29日 06:40/ 0 赞/ 321 阅读

相关如何判断一个数是否为素数

超级基础的题目，这里就不吐槽啦。那么怎么判断呢？假设这个数为num并且num=n\m; 因为n>Math.sqrt(num), 所以m<Math.sqrt(num)

你的名字/ 2022年05月24日 04:44/ 0 赞/ 326 阅读

相关 javascript判断一个数是否是素数(质数)

//素数(质数)：只能被1 和其本身整除的数 //用户输入一个数，判断这个数是否是素数 //方案一：因子一定有两个 var num = N

小咪咪/ 2022年05月18日 09:27/ 0 赞/ 387 阅读

相关 c#判断一个数是否是素数

素数是只能被1或本身整除，且不能为其他两个整数的乘积。1、2、3本身就是素数，判断一个数是否为素数，只需要用这个值依次除以2到它的开方数，如果其中有一个数可以整除，那么该值不为

红太狼/ 2022年05月16日 09:23/ 0 赞/ 393 阅读