精华内容
下载资源
问答
  • 素数判断

    千次阅读 2017-11-30 12:59:13
    在Raptor的某些问题中,会有判断素数或者找出某一区间范围内的素数,这样的问题比较多,因此本篇内容讲解怎么判断一个数是不是素数 ...因为素数判断用到的比较多,所以我们从方便的角度定义一个素数判断的子程序isPri

    1.问题背景

        在Raptor的某些问题中,会有判断素数或者找出某一区间范围内的素数,这样的问题比较多,因此本篇内容讲解怎么判断一个数是不是素数

    2.实现原理

    定义:质数(prime number)又称素数,质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。如果一个数有除了1和自身的其他因子就被称为合数。

    • 因为素数判断用到的比较多,所以我们从方便的角度定义一个素数判断的子程序isPrime(in n,out flag),如下图所示:
      这里写图片描述

    • 根据因数分解我们知道如果n可以分解为p*q(假定q>p),那么一定有p<=sqrt(n),q>=sqrt(n),这是显然的

    • 我们先假定这个数是素数,令flag=1,根据素数的定义,我们只需要定义一个循环变量i从2到sqrt(n)循环判断是不是存在能整除n的数,Raptor判断整除的条件是这样的 n mod i=0,如果条件成立,那么说明存在能整除n的一个数,那么我们令flag=0,如下图:
      这里写图片描述

    • 现在就看循环退出的条件了

      • 因为这是一个判断素数的子程序,当我们知道了flag=0,也就是这个数不是素数是合数,就让程序退出
      • 同时这个循环变量i已经大于sqrt(n)也让程序退出
        这里写图片描述
    • 到这里我们就完成了整个子程序的过程了

    3.应用例子及结果展示

        给出[m,n]区间上所有的素数,m和n为从输入框输入的整数

    分析:
        上面我们一定编写好了判断一个数是不是素数的子程序,我们只需要对从m到n的整数进行遍历就好了 ,然后每一次进行调用子程序

    • 比如我们寻找20到50之间的所有素数,我们输入m=20,n=50
      这里写图片描述

    • 比如我们 寻找所有不大于80的素数,我们输入m=2,n=80
      这里写图片描述

    4.流程图

    • 主程序:
      这里写图片描述

    • 判断素数子程序:
      这里写图片描述


        以上是判断一个数是不是素数的子程序以及简单的应用的例子讲解,需要本程序、需要代做Raptor程序或者有其他什么问题请联系QQ545030769

    展开全文
  • Java素数判断

    2021-04-09 11:40:41
    java素数判断(布尔类型) 判断一个数字是否为素数,要求在控制台输入一个数字,程序运行结束后输出该数字是否为素数。 素数定义:除了 1 和数字本身没有其他因数的数字 运行:

    java素数判断(布尔类型)


    判断一个数字是否为素数,要求在控制台输入一个数字,程序运行结束后输出该数字是否为素数。

    素数定义:除了 1 和数字本身没有其他因数的数字

    在这里插入图片描述

    运行:

    在这里插入图片描述

    展开全文
  • python素数判断

    2020-02-27 18:21:28
    素数判断 import math def is_prim(num): #判断素数 is_prime = True for i in range(2,int(math.sqrt(num))+1): if num%i==0: is_prime = False break if is_prime ...

    素数判断

    import math
    def is_prim(num):           #判断素数
        is_prime = True
        for i in range(2,int(math.sqrt(num))+1):
            if num%i==0:
                is_prime = False
                break
        if is_prime and num>1:
            return True
        else:
            return False
    
    >>> is_prim(17)
    True
    >>> is_prim(18)
    False
    
    展开全文
  • 快速素数判断算法

    千次阅读 2019-02-16 15:51:44
    快速素数判断算法素数的一些性质吧C++代码实现与解析 最近在复习之前做的编程练习题,素数判断一直没有掌握,今天看到了一种新的方法,感觉特别好,记下来。(第一次写博客,很开心呀) 思想来源,看不懂我的,欢迎...

    欢迎访问最新博客地址

    最近在复习之前做的编程练习题,素数判断一直没有掌握,今天看到了一种新的方法,感觉特别好,记下来。(第一次写博客,很开心呀)
    思想来源,看不懂我的,欢迎看原作

    素数的一些性质吧

    1. 素数的分布规律
      大于5的素数一定于6的倍数相邻,例如5和7,11和13,17和19等等。
    2. 证明
      令 x ≥ 1,则大于5的自然数可以表示如下:
      …6x-1, 6x, 6x+1, 6x+2, 6x+3, 6x+4, 6x+5,6(x+1)-1…
      可以看到,不在6的倍数的两侧的6x+2, 6x+3, 6x+4,由于上式可表示为2(3x+1), 2(2x+3), 2(3x+2),So 他们一定不是素数,在除去6x本身,显然素数只能出现在6的倍数的两侧,但这只是素数的必要条件可不是充分必要条件,所以在6的倍数的两侧的数也不一定素数。
    3. 孪生素数
      题外话,放个题拿走练练

    C++代码实现与解析

    明确目的: 找到可以整除的数(这很重要)
    实现:

    • 首先对两个较小的素数进行处理
    • 接下来判断这个数是否在6的倍数的两侧,不是的话直接返回0,是的话接着处理
    • 由于一个数N如果可以被另一个数m整除,那m一定小于N的开方,没啥问题。所以我们就取判断的上界为N的开方。为了更快呢,直接取 i 的每次递增6,原因是,假如要判断的数为N,那N一定可以表示为6x-1或6x+1,对于循环中的 i 也可以表示为6的倍数加上或减去个数字,即6m-1,6m,6m+1,6m+2,6m+3,6m+4,如果N能被6m,6m+2,6m+4,整除那N至少是一个偶数,显然第二步已经把偶数排除了,所以不可能成立,而对于6m+3如果成立则N至少是3的倍数,但6x是3的倍数,显然6x+1,6x-1可能被3整除,所以N也不可能被6m+3整除,那现在就只剩下了6m-1,6m+1了,只需判断它俩能否把N整除,如果可以那就存在了一个数可以把N整除,就返回0。反之就不存在了,那就走到了最后就返回1,哈哈大功告成。
    bool isPrime(int num)
    {
        // 两个较小的数另外处理
        if(num == 2 || num == 3)
        {
            return 1;
        }
        // 不在6的倍数的两侧的一定不是素数
        if(num % 6 != 1 && num % 6 != 5)
        {
            return 0;
        }
        int tem = (int)sqrt(num);
        //在6的倍数的两侧的也不一定是素数
        for(int i = 5;i <= tem;i += 6)
        {
            if(num % i == 0 || num % (i + 2) == 0)
            {
                return 0;
            }
        }
        // 排除所有剩余的是素数
        return 1;
    }
    

    人生第一篇博客,如有错误欢迎指正讨论。谢谢我自己,也谢谢大家
    在这里插入图片描述

    展开全文
  • 素数判断算法

    2015-06-26 19:55:36
    素数判断算法   一. 朴素判断素数 二. 筛选法 三. 费马素数测试 四. 米勒拉宾素性测试
  • 回文素数判断

    2018-04-11 17:23:56
    //回文素数 //1.素数,2.回文 //遍历+条件 #include&lt;stdio.h&gt; #include&lt;math.h&gt; long re(long n)//倒置 { int t=0; while(n&...int pri(long m)//素数判断 { long n=sqr...
  • 大数计算器及素数判断,c++带代码及word讲解,简短易懂!
  • C语言之素数判断及输出

    多人点赞 热门讨论 2021-05-16 22:25:10
    C语言之素数判断 我们要想解决素数问题首先要明确素数是什么。 文章目录C语言之素数判断什么是素数如何计算素数素数源代码 什么是素数 素数:素数一般指质数。质数是指在大于1的自然数中,除了1和它本身以外不再有...
  • 素数判断详解

    2017-06-06 13:56:26
    素数判断详解参考文章:点击打开链接对于判断素数大概有两类方法1:试除法2:筛选法还有一个米勒-拉宾检验方法此处不再展开。试除法:不断地尝试能否整除。比如要判断自然数 x 是否质数,就不断尝试小于 x 且大于1的...
  • 11.素数判断及打印素数表-优化版

    千次阅读 2020-01-18 15:22:36
    11.素数判断及打印素数表-优化版 1. 素数判断 素数定义:除了1和本身以外,不能被任何其他整数整除的一类数; 如果这个数X,isprime(x)返回1则是素数 返回0则非素数 int isprime(int x) { if(x<=1) return 0; ...
  • C语言素数判断算法分析

    千次阅读 2019-11-08 16:41:07
    C语言素数判断算法分析 1、素数的定义 素数:也叫质数,是指大于1,且只能被1和它自身整除的自然数; 1既不是素数,也不是合数; 2是最小的素数; 2、三种算法分析 2.1 最简单最易懂的判断方法 2,3是...
  • # 素数判断 v = float(input("输入一个大于2的值")) init = 2 while init <= (v-1): if v % init == 0: print("不是素数") break elif init == (v-1): print("这个数是素数") init += 1
  • 使用python实现素数判断

    千次阅读 2019-12-27 16:48:16
    使用python实现素数判断1、素数的特点2、代码实现3、运行结果 1、素数的特点 素数就是除了1和它本身,不能被其他数整除的数。 2、代码实现 #在控制台录入一鼐整数,判断是否为素数. #只能被1和自身整除的数字 #例如...
  • 素数判断程序

    2017-12-05 16:22:34
    该程序为判断素数的一个小的C语言程序,可以让大家参考。
  • 素数判断 bool is_prime(int n) { if (n < 2)return false; if (n == 2 || n == 3)return true; if ((n + 1) % 6 != 0 && (n - 1) % 6 != 0) return false;//5以后的素数肯定在6的倍数旁边, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,614
精华内容 5,845
关键字:

素数判断