判断一个数是不是质数(素数),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)


相关推荐

  • win10企业版永久激活方法「建议收藏」

    win10企业版永久激活方法「建议收藏」win10企业版永久激活方法?win10企业版是针对企业用户推出的版本,随着win10系统的不断完善,现在越来越多的人选择升级win10,升级完系统就需要激活它。那么今天就为大家分享一下怎么永久激活w

  • linux下DNS配置及域名解析服务

    linux下DNS配置及域名解析服务一.DNS(DomainNameSystem,域名系统)    因特网上作为域名和IP地址相互映射的一个分布式数据库,能够使用户更方便的访问互联网,而不用去记住能够被机器直接读取的IP数串。通过主机名,最终得到该主机名对应的IP地址的过程叫做域名解析(或主机名解析)。DNS协议运行在UDP协议之上,使用端口号53。    DNS服务器将域名解析出来,找到域名对应的ip地址的…

  • python获取股票历史数据_量化交易之如何获取股票历史数据并存为csv

    python获取股票历史数据_量化交易之如何获取股票历史数据并存为csv量化研究尤其是进行基于价值投资的量化研究,需要上市公司的历史估值数据,如市盈率PE,市净率PB,或者市销率PS,市现率PCF。而有的人喜欢用exce或者csv文件的格式存放数据并且分析。我这里介绍一个网站,BaoStock,既支持直接下载历史数据为csv,也支持用程序下载数据并生成csv格式。网站地址是www.baostock.com,如果要下载历史估值数据,进入首页后,选择“沪深A股估值指标(日…

  • 不通过浏览器获取公网 IP

    不通过浏览器获取公网 IP

  • 【Android动画】之Tween动画 (渐变、缩放、位移、旋转)

    【Android动画】之Tween动画 (渐变、缩放、位移、旋转)

  • 学习双拼必看(最全教程):双拼输入法的心得以及快速入门办法

    学习双拼必看(最全教程):双拼输入法的心得以及快速入门办法1.简单介绍一下双拼2.总共18种双拼方案3.15种双拼方案的具体映射4.顺便提一下双拼口诀的事情5.总结不同平台选择的方案双拼(也称双打)是一种建立在拼音输入法基础上的输入方法,可视为全拼的一种改进,它通过将汉语拼音中每个含多个字母的声母或韵母各自映射到某个按键上,使得每个音都可以用两个按键打出,极大地提高了拼音输入法的输入速度。这种声母或韵母到按键的对应表通常称之为双…

发表回复

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

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