如何判断一个数是否为素数(判断一个数为素数)

目录1.什么是质数?2.如何判断是否为质数?方法1方法2方法3方法41.什么是质数?首先来看质数的概念:质数(Primenumber),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。(也可定义为只有1与该数本身两个正因数的数)图1数字12不是质数,而数字11是质数如上图所示,数字12可以将每4个分成一组,…

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

目录

1.什么是质数?

2.如何判断是否为质数?

方法1

方法2

方法3

方法4


1.什么是质数?

首先来看质数的概念:

质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。(也可定义为只有1与该数本身两个正因数的数)

 

如何判断一个数是否为素数(判断一个数为素数)
图1  数字12不是质数,而数字11是质数

如上图所示,数字12可以将每4个分成一组,一共3组;而数字11将每4个、每5个、每3个分成一组都无法全部分完,而有剩余,因此将数字11称为质数。

 

2.如何判断是否为质数?

质数的特点如下:

一个自然数(如1、2、3、4、5、6等)若恰有两个正约数(1及此数本身),则称之为质数。

方法1

根据质数的约数只有1和本身这一特点,可以首先想到最直观的方法。第一种方法就是判断一个数是否能被比它小的数整除

方法1的时间复杂度是O(n)。

public static boolean isPrime(int n){
    //n<=3时,质数有2和3
    if (n <= 3) {
        return n > 1;
    }
    //当n>3时,质数无法被比它小的数整除
    for(int i = 2; i < n; i++){
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

方法2

当一个数不是质数时,必定存在两个约数,一个大于等于sqrt(n),另一个小于sqrt(n)。利用这种特性,可以对方法1进行改进,只判断数n能否被小于sqrt(n)的数整除。

方法2的时间复杂度是O(sqrt(n))。

如何判断一个数是否为素数(判断一个数为素数)
图2  筛选判断集,只选择小于等于sqrt(n)的集合

 

public static boolean isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    //判断一个数能否被小于sqrt(n)的数整除
    int sqrt = (int)Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

方法3

任一偶数一定能分解为2和其他偶数/奇数的积,因此一个数不能被2整除,那么这个数一定不能被其他偶数整除。利用这个特点,可以对方法2进行改进,判断数n能否被小于sqrt(n)的奇数整除。

方法3的时间复杂度是O(sqrt(n)/2)。

如何判断一个数是否为素数(判断一个数为素数)
图3  进一步筛选判断集,只选择小于等于sqrt(n)的奇数
public static boolean isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    //只需判断一个数能否被小于sqrt(n)的奇数整除
    int sqrt = (int)Math.sqrt(n);
    for (int i = 3; i <= sqrt; i += 2) {
        if(n % 2 == 0 || n % i == 0) {
            return false;
        }
    }
    return true;
}

方法4

质数的分布具有特点,经过证明可以得到,(大于等于5的)质数一定和6的倍数相邻,一定是6x-1或6x-1。利用这种特性。可以对整数进行筛选,只判断那些是6x-1或6x-1的整数是否为质数。

如何判断一个数是否为素数(判断一个数为素数)
图4  筛选数据集,只选择6的倍数相邻的数

证明过程如下:

令x≥1,将大于等于5的自然数表示如下: ······6x-1,6x,6x+1,6x+2,6x+3,6x+4······(相邻6个数为一组)

在以上的数字中,6x、6x+2和6x+4是偶数,一定不是质数;6x+3可以分解为3(2x+1),不是质数,因此质数只能是6x-1和6x+1。

public static boolean isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    // 只有6x-1和6x+1的数才有可能是质数
    if (n % 6 != 1 && n % 6 != 5) {
        return false;
    }
    // 判断这些数能否被小于sqrt(n)的奇数整除
    int sqrt = (int) Math.sqrt(n);
    for (int i = 5; i <= sqrt; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

 

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

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

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

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

(0)


相关推荐

  • 15种手机游戏引擎和开发工具介绍

    15种手机游戏引擎和开发工具介绍工欲善其事,必先利其器。对移动游戏开发者来说,高效实用的开发工具必不可少。近日,英国著名产业杂志《Develop》刊出了一篇文章,作者艾伦·李在文中推荐了15种移动游戏开发工具,从游戏引擎,到音效制作、推广等工具都有涉及。以下为原文主要内容编译。引擎和移动开发工具包Marmalade简介:Marmalade被很多人认为是跨平台制作C++游戏的最佳平台。通过MarmaladeSDK,开发者可以在单一的Marmalade项目文件夹中打开Xcode或VisualStudio,将

  • PHP在线客服系统平台源码(完全开源的网页在线客服系统)

    PHP在线客服系统平台源码(完全开源的网页在线客服系统)  在线客服系统是一个使用PHP、JavaScript和CSS开发的即时网页聊天咨询系统。该项目包含管理员和用户端。管理员端管理所有的管理,如编辑站点内容、管理提供者和预订,管理员在这个系统的管理中起着重要的作用。    在线客服系统源码及演示:zxkfym.top    对于用户部分,用户可以浏览主页、关于和服务。用户可以是顾客谁需要家庭服务或服务提供商提供家庭服务的人。为了注册为服务提供商,用户必须填写注册表格。然而,要将服务提供商作为客户预订,用户可以先搜索可用的服务提供商,然后再进行预订。该

  • 2019工程伦理慕课答案(2019秋)习题及期末答案

    2019工程伦理慕课答案(2019秋)习题及期末答案第一章习题(下)单选题(1/1point)下列哪一项不是工程与技术的区别内容和性质目的活动主体任务、对象和思维方式单选题(1/1point)下列哪一项不是工程活动的特征自主性创造性社会性确定性多选题(1points)下列哪项是工程的完整生命周期中的环节计划设计评估完成判断题(1/1point)计划、设计、建造…

  • nginx 转发websocket_nginx配置websocket

    nginx 转发websocket_nginx配置websocketnginx入门之简易,相信用过的同学都会有体会,没有复杂安装,没有庞大的配置文件,在nginx.conf配置一下,就可以提供不同类型的服务。本文简单描述下如何转发(反向代理)一个socket服务。将要配置一个如上图示的转发服务。在nginx.conf文件,与events平行的级别,配置一个stream#evnets是配置文件已有内容events{ worker_connec…

  • javascript 向数组中添加数组元素(输入元素,不太重要)「建议收藏」

    javascript 向数组中添加数组元素(输入元素,不太重要)「建议收藏」javascript中向数组中输入元素,基本上有三种方式。1、在定义数组对象的时候,直接输入元素,varlist=newArrey(1,2,3,’内容’)2、利用数组对象的元素下标向其中输入数组元素list=newArray(9)list[2]=2list[3]=3这样list的下标是2与3的内容就添加上值了。3、可以利用for语句向数组对象中输入数组元素可以批量向数组对象中输入数组元素,一般用于对数组对象赋初始值,例如,可以通过改变变

  • hadoop入门教程列表

    hadoop入门教程列表最近也在看hadoop,搜集了一些入门的教程。感觉不错。写在这里分享下。1、从安装到实例以及基本的原理都有涉及:虾虾皮hadoop系列入门。2、一份不错的单节点hadoop搭建环境以及运行WordCount的教程:running-hadoop-on-ubuntu-linux-single-node-cluster 。3、Eclipse远程编译运

发表回复

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

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