判断一个数是不是质数(素数),3种方式介绍

一、概念介绍大家中学都学过,就不过多介绍了,大致提两点:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。 0和1既不是质数也不是合数,最小的质数是2二、方法介绍1.最直观,但效率最低的写法publicstaticbooleanisPrime(intn){if(n<=…

大家好,又见面了,我是你们的朋友全栈君。

一、概念介绍

    大家中学都学过,就不过多介绍了,大致提两点:

  •     质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。
  •     0和1既不是质数也不是合数,最小的质数是2

 

二、方法介绍

1.最直观,但效率最低的写法

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

    这里特殊处理了一下小于等于3的数,因为小于等于3的自然数只有2和3是质数。

    然后,我们只需要从2开始,一直到小于其自身,依次判断能否被n整除即可,能够整除则不是质数,否则是质数。

 

2.初步优化

    假如n是合数,必然存在非1的两个约数p1和p2,其中p1<=sqrt(n),p2>=sqrt(n)。由此我们可以改进上述方法优化循环次数。如下:

public static 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;
}

 

3.继续优化

    我们继续分析,其实质数还有一个特点,就是它总是等于 6x-1 或者 6x+1,其中 x 是大于等于1的自然数。

    如何论证这个结论呢,其实不难。首先 6x 肯定不是质数,因为它能被 6 整除;其次 6x+2 肯定也不是质数,因为它还能被2整除;依次类推,6x+3 肯定能被 3 整除;6x+4 肯定能被 2 整除。那么,就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。所以循环的步长可以设为 6,然后每次只判断 6 两侧的数即可。

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;
}

    对于输入的自然数 n 较小时,也许效果不怎么明显,但是当 n 越来越大后,该方法的执行效率就会越来越明显了。
    

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124563.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mysql8和mariadb_mariadb迁移到mysql

    mysql8和mariadb_mariadb迁移到mysqlMariaDB为可替代MySQL的增强版本,但在已安装了MySQL的情况下同时也能安装MariaDB.(这是有意义的,例如你想从一个数据库/应用迁MariaDB为可替代MySQL的增强版本,但在已安装了MySQL的情况下同时也能安装MariaDB.(这是有意义的,例如你想从一个数据库/应用迁移到另一个数据库/应用中.)以下是在已安装MySQL的情况下,安装MariaDB的主要步骤.下载…

    2022年10月24日
  • 数据库char转int_mysql string转int

    数据库char转int_mysql string转int展开全部首先char类型的必须是数字,将字符的数32313133353236313431303231363533e58685e5aeb931333431373262字转成数字,比如’0’转成0可以直接用加法来实现;例如:将pony表中的d进行排序,可d的定义为varchar,可以这样解决;select*fromponyorderby(d+0);在进行ifnull处理时,比如ifnu…

  • Spring整合Sharding-JDBC分库分表详情

    Spring整合Sharding-JDBC分库分表详情Spring整合Sharding-JDBC分库分表详情一、概述最初线上系统的业务量不是很大,业务数据量并不大,比如说单库的数据量在百万级别以下(事实上千万级别以下都还能支撑),那么MySQL的单库即可完成任何增/删/改/查的业务操作。随着业务的发展,单个DB中保存的数据量(用户、订单、计费明细和权限规则等数据)呈现指数级增长,那么各种业务处理操作都会面临单DB的IO读写瓶颈带来的性能问题。S…

  • Java代码生成器[通俗易懂]

    Java代码生成器[通俗易懂]项目说明本项目基于是基于renren-generator定制的代码生成器文章目录**项目说明**不同点:效果原理分析如何定制开发?更多可能存在的坑代码地址不同点:因为本人的公司使用的是tkmyabtis+swagger构建restapi,而renren-generator用的是mybatis-plus,而且不支持swagger,所以有了本项目效果…

  • 五笔结构与识别码_五笔打字识别码怎么区分

    五笔结构与识别码_五笔打字识别码怎么区分4.末笔字型识别码表末笔笔画只有五种,字型信息只有三类,因此末笔字型交叉识别码只有15种如表4-1所示。表4-1末笔字型识别码表左右型1上下型2杂合型3横111G一12F二

  • 开源微服务编排框架:Netflix Conductor「建议收藏」

    开源微服务编排框架:Netflix Conductor「建议收藏」简介:本文主要介绍netflixconductor的基本概念和主要运行机制。​作者|夜阳来源|阿里技术公众号本文主要介绍netflixconductor的基本概念和主要运行机制。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号