精华内容
下载资源
问答
  • 判断一个数是不是质数(素数),3种方式介绍

    万次阅读 多人点赞 2018-06-10 09:56:59
    一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的叫做质数;否则称为合数。 0和1既不是质数也不是合数,最小的质数是2 二、方法介绍 1.最直观,但效率最低的写法 public static boolean ...

    一、概念介绍

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

    •     质数又称素数。一个大于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 越来越大后,该方法的执行效率就会越来越明显了。
        

    展开全文
  • 判断一个数质数

    2019-12-05 21:37:35
    判断一个数质数 i=int(input(‘请输入一个数字’)) while(i<2): if(i1): print(“不是质数也不是和数”) elif(i<2): print(“输入大于二的”) break else: if(i2): print(“是质数”) elif(i%2...

    判断一个数是质数

    “质数(prime number)又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。

    
    i=int(input('请输入一个数字'))
    while(i<2):
        if(i==1):
            print("不是质数也不是和数")
        elif(i<2):
            print("输入大于二的数")
        break
    else:
        if(i==2):
            print("是质数")
        elif(i%2==0):
            print("不是质数")
        else:
            print("质数")
    展开全文
  • 判断 一个数 是不是 质数 / 素数

    千次阅读 2019-12-27 15:28:38
    判断 一个数 是不是 质数 / 素数 【面试必备 100题 系列 】- 001 - 判断 一个数 是不是 质数 / 素数 一、命题分析: 质数又称素数。指整数在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除...

    判断 一个数 是不是 质数 / 素数

     

    【面试必备 100题 系列 】- 001 - 判断 一个数 是不是 质数 / 素数

     

    一、命题分析:

       质数 又称 素数。指整数在一个大于1的 自然数 中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为 合数 。1和0既非素数也非合数。素数在 数论中有着很重要的作用。

    二、答案解析:

    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的自然数
     */

        基于这个理论我们不难推算出:

            a、能被 6 整除的,肯定不是质数/ 素数,可以肯定的是,6x 不是质数/ 素数;

            b、能被  2 / 3 整除的,肯定不是 质数/ 素数, 因此,6x+2 / 6x+3/ 6x+4  肯定也不是质数/ 素数;

    那么,就剩下 6x+16x+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;
    }


     

    展开全文
  • 循环练习题1:输入一个数判断一个数是不是质数,如果是质数输出"YES",否则输出"NO"? 1.质数的性质? 解题思路 代码 质数就是因数除了1和本身以外没有别的因数,那么质数的因数个就只有两个。 如果想判断...

    循环练习题1 c++实现:输入一个数判断一个数是不是质数,如果是质数输出"YES",否则输出"NO"?

    • 1.质数的性质?
      • 解题思路
        • 代码
    1. 质数就是因数除了1和本身以外没有别的因数,那么质数的因数个数就只有两个。
    2. 如果想判断这个数是不是质数,我们只需要找出这个数的所有因数,如果因数的个数等于2就可以判断出这个数是质数,否者就不是质数。
    3. 输入一个数判断一个数是不是质数,如果是质数输出"YES",否则输出"NO"
      代码

    输入样例
    3
    输出样例
    YES
    输入样例
    4
    输出样例
    NO

    代码

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
    	int n,d=0;
    	cin>>n;  //输入判断的数
    	for(int i=1;i<=n;i++)
    	{
    		if(n%i==0)  //判断i是不是N的因数 
    		{
    			d++;  //记录n因数的个数 
    		}	
    	}
    	if(d==2)  //如果d等于2就可以说是因数 
    	{
    		cout<<"YES";
    	}
    	else
    	{
    		cout<<"NO";
    	}
    	return 0;
    }
    
    

    自己随意写的,欢迎大家留言,希望能帮助到大家。

    展开全文
  • 标题 判断一个数质数或合数 bool isnum(long long n) { long long j;//若一个数为合数,那么至少可以写成n=j*j;或者为两个自然数, 一个大于sqrt(n),一个小于; for(j=2;j*j<=n;j++)//判断n在0~sqrt(n)的...
  • JS中判断一个数是否是质数

    千次阅读 2018-05-01 23:27:16
    判断一个数是否是质数 var n = parseInt(prompt("请输入一个正整数")); var sum = 0; for(var i = 1 ; i &lt;= n ; i++){ if(n % i == 0){ sum++; } } if(sum == 2){ console.log(n + &...
  • 编制质数表的过程是:按照自然数列,第一个数1不是质数,因此要除外,然后按顺序写出2至100的所有自然数,这些中2是质数,把它留下,把2后面所有2的倍数划去,2后面的3是质数,接着再把3后面所有3的倍数划去,如此...
  • 正确而迅速地判断一个自然数是不是质数,在的整除性这部分知识中,是一项重要的基本技能。  由于大于2的质数一定是奇数(奇数又不一定都是质数),所以,在判断一个自然数是不是质数时,首先要看它是奇数还是偶数...
  • // 判断一个数是否为质数的函数(质数,只能被1和他本身整除的) // 判断方法,如果一个数在2到他本身开根号之间的都无法整除,那么他就是一个质数 function zhishu(num){ var sqrt = Math.sqrt(num); ...
  •  System.out.println(num+"是质数");  }  else{  System.out.println(num+"不是质数");  }  }  public static long isPrime(long a){  for(int i = 2;i;i++){  if((Math.pow(i, a-1) % a)=...
  • python中判断一个数字是否是质数

    万次阅读 2017-09-02 18:56:21
    判断一个数是否是质数,有很多方法,几乎每一种语言都有关于判断是否是质数的算法,今天我向大家分享python中如何判断一个数字是否是质数:首先要明白什么是质数,质数一个只能被自己和1整除的大于1的正整数。...
  • 判断1000 000 00内的一个数是否是素数,比较优化一点的,i从2到sqrt(i)循环判断,效率不行,希望大神指点。
  • 质数也叫素数,是只能被1和它本身...判断一个数质数的最简单的方法如下: [code="Python"] def isPrime1(n): for i in range(2, n): if n % i == 0: return False return True [/code] ...
  • i一个变量;flag素数判断标识 scanf("%d",&m); for(i=2;i<m;i++) { if(m%i==0) { flag = 1; break; } } if(!flag) printf("%d 是素数",m); else printf("%d 不是素数",m); } ...
  • 判断一个输是不是质数,比较简单的方法有两种。 第一种: 质数的定义是:除了1和它本身,不能被其他任何整除,然后最小的质数是2。 代码如下: bool isPrime(int num) { if (num <= 3) { return num > 1;...
  • matlab程序 判断一个数是否为质数 参数以及详细描述都在代码里了
  • 质数的概念是小学学过的。...n = input("请输入一个数:") for x in range(2,n): if n % x == 0: print str(n)+"不是质数" break else: print str(n)+"是质数" break 请输入一个数:11 11是质数 ...
  • 质数:只能被1和本身整除的...以下是Java实现的判断一个数是否是质数的代码。class isPrime{ public boolean isPrimeNumber(int num){ if(num&lt;=2||num%2==0){ return false; } for(int i=3;i&lt;M...
  • 质数是除了1和它本身再无其他的因数,例如5。在数学上与质数相对的是合数。其中1既不是质数也不是合数。 新的改变 我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了...
  • function f1(n) { for (var i=2;i<n;i++){ if (n%i===0){ return "不是质数"; } } return "是质数"; } console.log(f1()) //f1()里面输入要判断的...
  • JAVA判断一个数是否为质数

    千次阅读 2019-10-09 21:17:41
    JAVA判断一个数是否为质数 输入一个正整数N,判断是不是质数,如果是质数输出“N是一个质数”,否则输出“N不是质数”。 提示:质数的含义:除了1和它本身不能被任何整除。(使用for循环实现) import ...
  • python判断一个数是否是质数

    千次阅读 2019-08-21 15:29:46
    一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除(2, 3, 5, 7等),换句话说就是该除了1和它本身以外不再有其他的因数。 num = int(input('请输入一个数字:')) if num>1: for test in ...
  • num1 = int(input("请输入一个整数,回车结束\n")) num2 = 2 #从能否被2整除开始 if num1 < 2 : #如果输入0或1,返回“NO” print("NO") exit() while num1 % num2 != 0: #循环到num1第一次被整除为止 num2 +=...
  • 质数一个大于1的,除了1和本身外,不能被其他自然数整除的,所以我们只需要获取到2到num之间的,再进行求余数,若余数为0,则一定不是质数,相反,我们只用默认输入的就是质数,然后用if设置不是质数的情况...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,756
精华内容 13,102
关键字:

如何判断一个数是质数