精华内容
下载资源
问答
  • 前言: 今天搞了一天这个 蒙格马利 什么,...判断一个数是否是质数? 解题思路: 一开始我想的方法就是用For循环一个一个判断,后来看资料说这是最笨的方法,好吧,我得承认我数学太渣 下面开始介绍点要用到

    前言:

    今天搞了一天这个 蒙格马利 什么的,我自己肯定是搞不定,参照了很多资料,写一下自己的理解总结,防止忘了没地方看。

    只是我个人的理解,对不对还得另说,一些公式还是不懂,只是大概的理解了下,各位当做参考吧

    问题描述:

    判断一个数是否是质数?

    解题思路:

    一开始我想的方法就是用For循环一个一个判断,后来看资料说这是最笨的方法,好吧,我得承认我数学太渣

    下面开始介绍点要用到的知识:

    1、积模分解公式:

    具体的我就不说了,而且我也不太懂,记住这个就好:((A%C)*(B%C))%C=(A*B)%C    这个公式是用来求 蒙格马利 函数

    举个例子:2^7%3       二的七次方模三        就可以换算成   ( (2^4%3)*(2^3%3))%3

    2、用蒙格马利判断是否是质数:

    例子:设要判断的数为num,  需要用若干个素数(也就是质数)做为参考数,假设某个素数集合为prime[] ,那么关键来了 

    如果   *素数集合中的每个素数数都能是这个式子成立*  即:prime[ ]^(num-1)%num==1,就可以大概说明num是个素数,反之则不是素数

    素数集合一般50个素数就可以了(这只是据说,我也不知道),反正就是集合中的素数越多 ,越精确

    代码:

    unsigned int Montgmery(unsigned int num, unsigned index, unsigned int mod)//蒙哥马利快速幂算法  (num^index)%mod
    {
    	unsigned int tmp = 1;//保存奇数是剩下的那个数
    	num %= mod;  // 假设(2^7)%3     2%3
    	while (index > 1)
    	{
    		if (index & 1)  //按位与 ,除最低位不变其他位置0 ,如果为1 说明是奇数,否则偶数
    		{
    			tmp = (tmp*num) % mod;// 假设(2^7)%3  第一次为 1%3=1  (1%3)(2%3)%3=2%3    第二次 为((2%3)*(4%3))%3=8%3
    		}
    		num = (num*num) % mod;//(2%3)(2%3)%3=4%3    (4%3)(4%3)%3=16%3
    		index /= 2;
    	}
    	unsigned result = (num*tmp) % mod;     //(16%3)(8%3)%3=(2^7)%3
    	return result;
    }
    上面这个就是求 A^B%C的C语言函数,这个是优化后的版本,若是不懂继续往下看


    int IsPrime(unsigned int num)//判断num是否是质数 ,如何是返回1,不是返回-1;
    {
    	if (num < 2)
    	{
    		return -1;
    	}
    	static unsigned int PrimeList[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ,37, 41,
    		                            43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
    	                               };//质数表
    	const int count = sizeof(PrimeList) / sizeof(unsigned int);//求出置数表中数的个数
    	//printf("%d\n", count);
    	int i = 0;
    	for (i = 0; i < count; i++)//循环质数表中的每一个数
    	{
    		if (num == PrimeList[i])//如果输入的数在质数表中则返回  这句绝对不能删,删了就不对了
    		{
    			return 1;
    		}
    		//printf("%d\n", Montgmery(PrimeList[i], num - 1, num));
    		if (Montgmery(PrimeList[i], num - 1, num) != 1)//按照表中的质素算,如果全都为1则可以大概说num是质数
    		{
    			return -1;
    		}
    	}
    	return 1;
    }
    上面这个呢就是 判断是否是质数的函数,质数表没弄太多,如果想要精确的话 弄500个质数应该差不多可以达到很精确了(当然这也是据说),特别要注意的是

    ***** 如果你输入的数等于质数表中的某个质数的话  (prime[ ]^(num-1)%num==1)这个公式就不成立了,我也不知道为什么,我参考的资料里没说这点,所以他的那个有点小问题,我在里面加了一个判断 如果num==PrimeList[],也就是你输入的数在素数表中,就返回一,说明已经是素数了**************

    void main()
    {
    	static unsigned  int aPrimeList[] = { // 素数表  
    		1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
    		43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 113,
    		193, 241, 257, 337, 353, 401, 433, 449, 577, 593, 641,
    		673, 769, 881, 929, 977, 1009, 1153, 1201, 1217, 1249,
    		1297, 1361, 1409, 1489, 1553, 1601, 1697, 1777, 1873,
    		1889, 2017, 2081, 2113, 2129, 2161, 2273, 2417, 2593,
    		2609, 2657, 2689, 2753, 2801, 2833, 2897, 3041, 3089,
    		3121, 3137, 3169, 3217, 3313, 3329, 3361, 3457, 3617,
    		3697, 3761, 3793, 3889, 4001, 4049, 4129, 4177, 4241,
    		4273, 4289, 4337, 4481, 4513, 4561, 4657, 4673, 4721,
    		4801, 4817, 4993, 5009, 5153, 5233, 5281, 5297, 5393,
    		5441, 5521, 5569, 5857, 5953, 6113, 6257, 6337, 6353,
    		6449, 6481, 6529, 6577, 6673, 6689, 6737, 6833, 6961,
    		6977, 7057, 7121, 7297, 7393, 7457, 7489, 7537, 7649,
    		7681, 7793, 7841, 7873, 7937, 8017, 8081, 8161, 8209,
    		8273, 8353, 8369, 8513, 8609, 8641, 8689, 8737, 8753,
    		8849, 8929, 9041, 9137, 9281, 9377, 9473, 9521, 9601,
    		9649, 9697, 9857
    	};
    	int count = sizeof(aPrimeList) / sizeof(unsigned int);
    	for (int i = 0; i < count; i++)
    	{
    		int ret = 0;
    		ret = IsPrime(aPrimeList[i]);
    		if (ret == 1)
    		{
    			printf("是质数\n", ret);
    		}
    		else
    		{
    			printf("不是质数\n", ret);
    		}
    	}
    	system("pause");
    
    }

    上面这段代码 是测试,我只测试了一堆素数,结果都对

    其他的也不想说了,我是参考别人的理解的 ,并发现了别人的有点小问题,已经在前面说了,如果你看不懂,推荐你还是看看这个人的吧,我就是参考他的

    http://blog.csdn.net/arvonzhang/article/details/8564836

    (当然 他也是参考别人的 !!!!!!!)


     








    展开全文
  • 这里有个巧妙的方法,由于3是质数,32位有符号整数int中最大3幂是1162261467, 即可根据1162261467 % n == 0来判断。 类似5 7 11 这样质数也同理(2除外,2幂可以通过n&n - 1 == 0 来判断 )。 bool ...

    由一道LeetCode题演变而来
    在这里插入图片描述
    思路:

    当然可以通过循环来实现,从1开始乘,每次乘3,即可。
    这里有个巧妙的方法,由于3是质数,32位有符号整数int中最大的3的幂是1162261467,
    即可根据1162261467 % n == 0来判断。
    类似5 7 11 这样的质数也同理(2除外,2的幂可以通过n&n - 1 == 0 来判断 )。

    bool isPowerOfThree(int n) {
        if (n < 1)
            return false;
        return 1162261467 % n == 0;
    }
    
    展开全文
  • 在好的程序算法中,快速判断是否是质数,能减少复杂度,减少运算时间,下面是一种优化方法。package com.realjt.smart; /** * 判断质数的方法 * * @author RealJt * @date 2018年6月17日 */ public...

    在大于1的自然数中,除了1和它本身以外不再有其他因数,这种自然数称之为质数或素数,例如2,3,5,7,11,13...有无限个。

    在好的程序算法中,快速判断是否是质数,能减少复杂度,减少运算时间,下面是一种优化方法。

    package com.realjt.smart;
    
    /**
     * 判断质数的方法
     *
     * @author RealJt
     * @date 2018年6月17日
     */
    public class PrimeNumber
    {
    	/**
    	 * 普通判断方法,在大于1的自然数中,除了1和它本身以外不再有其他因数
    	 * 
    	 * @time 时间复杂度O(n)
    	 * 
    	 * @param number
    	 * @return
    	 */
    	public static boolean isPrimeNumberNormal(int number)
    	{
    		if (number <= 1)
    		{
    			return false;
    		}
    
    		if (2 == number || 3 == number || 5 == number)
    		{
    			return true;
    		}
    
    		for (int i = 2; i < number; i++)
    		{
    			if (number % i == 0)
    			{
    				return false;
    			}
    		}
    
    		return true;
    	}
    
    	/**
    	 * 优化后的方法,一个整数能被两个因数分解,那么其中一个因数一定小于等于该数开平方根数,另一个因数一定大于等于该数开平方根数,并且去掉偶数的判断
    	 * 
    	 * @time 时间复杂度O(sqrt(n)/2)
    	 * 
    	 * @param number
    	 * @return
    	 */
    	public static boolean isPrimeNumberOptimize(int number)
    	{
    		if (number <= 1)
    		{
    			return false;
    		}
    
    		if (2 == number || 3 == number || 5 == number)
    		{
    			return true;
    		}
    
    		if (number % 2 == 0)
    		{
    			return false;
    		}
    
    		double squareRoot = Math.sqrt(number);
    		for (int i = 3; i <= squareRoot; i += 2)
    		{
    			if (number % i == 0)
    			{
    				return false;
    			}
    		}
    		return true;
    	}
    
    	/**
    	 * 优化后更快的方法
    	 * 
    	 * 自然数可以表示为6x,6x+1,6x+2,6x+3,6x+4,6x+5,其中x为大于等于0的整数
    	 * 由于6x=2(3x),6x+2=2(3x+1),6x+3=3(2x+1),6x+4=2(3x+2),故这四类数不可能为质数
    	 * 那么剩下6x+1和6x+5两类整数才可能是质数,即在6的倍数相邻两侧的整数才可能是质数,但在6的倍数相邻两侧的整数并不是一定就是质数,例如25
    	 * 
    	 * 假设要被判断的数为number=6x+1或6x+5,循环判断比numnber更小的数
    	 * 小于sqrt(n)需要判断是否能被整除的数可分为6i,6i+1,6i+2,6i+3,6i+4,6i+5六类
    	 * 
    	 * 如果number能被6i,6i+2,6i+4整除,则number得是一个偶数,显然number=6x+1或6x+5不可能是偶数,故不用判断number是否能被这三类数整除
    	 * 如果number能被6i+3整除,则number至少能被3整除,但是6x能被3整除,number=6x+1或6x+5不可能被3整除,故不用判断number是否能被6i+3整除
    	 * 剩下只需要判断number是否能被6i+1和6i+5整除,即5和7,11和13,设置步长为6
    	 * 
    	 * @time 时间复杂度O(sqrt(n)/3)
    	 * 
    	 * @param number
    	 * @return 是否是质数
    	 */
    	public static boolean isPrimeNumberFast(int number)
    	{
    		if (number <= 1)
    		{
    			return false;
    		}
    
    		if (2 == number || 3 == number || 5 == number)
    		{
    			return true;
    		}
    
    		// 不在6的倍数两侧的一定不是质数
    		if (number % 6 != 1 && number % 6 != 5)
    		{
    			return false;
    		}
    
    		// 在6的倍数两侧的也可能不是质数
    		double squareRoot = Math.sqrt(number);
    		for (int i = 5; i <= squareRoot; i += 6)
    		{
    			if (number % i == 0 || number % (i + 2) == 0)
    			{
    				return false;
    			}
    		}
    
    		return true;
    	}
    
    	public static void main(String[] args)
    	{
    		int range = 500000;
    		int total = 0;
    
    		long startTime = System.currentTimeMillis();
    		for (int i = 1; i <= range; i++)
    		{
    			if (isPrimeNumberNormal(i))
    			{
    				System.out.println(i);
    				total++;
    			}
    		}
    		System.out.println("time: " + (System.currentTimeMillis() - startTime) + " total: " + total);
    
    		total = 0;
    		startTime = System.currentTimeMillis();
    		for (int i = 1; i <= range; i++)
    		{
    			if (isPrimeNumberOptimize(i))
    			{
    				System.out.println(i);
    				total++;
    			}
    		}
    		System.out.println("time: " + (System.currentTimeMillis() - startTime) + " total: " + total);
    
    		total = 0;
    		startTime = System.currentTimeMillis();
    		for (int i = 1; i <= range; i++)
    		{
    			if (isPrimeNumberFast(i))
    			{
    				System.out.println(i);
    				total++;
    			}
    		}
    		System.out.println("time: " + (System.currentTimeMillis() - startTime) + " total: " + total);
    	}
    
    }
    

    3次执行结果


    源自 https://blog.csdn.net/huang_miao_xin/article/details/51331710,由RealJt整理。

    展开全文
  • 文章目录写在开头判断是否质数题目分析写在最后话: 这里是一段防爬虫文本,请读者忽略。 本文原创首发于CSDN,作者IDYS 博客首页:https://blog.csdn.net/weixin_41633902/ 本文链接:...


    这里是一段防爬虫文本,请读者忽略。
    本文原创首发于CSDN,作者IDYS
    博客首页:https://blog.csdn.net/weixin_41633902/
    本文链接:https://blog.csdn.net/weixin_41633902/article/details/107440905
    未经授权,禁止转载!恶意转载,后果自负!尊重原创,远离剽窃!
    


    写在开头的话

    • 请记住:实践是掌握知识的最快方法
    • 如果你只是怀着看看的态度去快速浏览文章,而不去认认真真的把文章里面讲的任何一个知识点去实践一遍,那么你永远也掌握不了它
    • 生命不息,折腾不止!

    判断是否为质数

    题目

    • 输入一个数判断其是否为质数

    分析

    • 解析
    1. 对用户输入进行判断,看其是否合法
    2. 依次除以比这个数的一半+1更小的数,判断是否能够整除,并且除数不为1
    • 源码
    def judegenum():
        try:
            num = int(input("请输入一个数\n"))
        except ValueError:
            print("您输入的值有误")
            exit(-1)
        i = 1
        while(i <= (num // 2 + 1)):
            if (num % i == 0):
                if i!=1 :
                    print("数字", num, "这不是质数")
                    exit(0)
            if(i == (num //2 +1)):
                    print("数字",num,"这是是质数呀")
            i+=1
            
    if __name__ == '__main__':
        judegenum()
    
    • 运行结果
    请输入一个数
    121
    数字 121 这不是质数
    


    写在最后的话:

    • 无论每个知识点的难易程度如何,我都会尽力将它描绘得足够细致
    • 欢迎关注我的CSDN博客,IDYS’BLOG
    • 持续更新内容
      linux基础 | 数据通信(路由交换,WLAN) | Python基础 | 云计算
    • 如果你有什么疑问,或者是难题。欢迎评论或者私信我。你若留言,我必回复!
    • 虽然我现在还很渺小,但我会做好每一篇内容。谢谢关注!

    展开全文
  • 对于30以内质数,大部分老师都会要求学生记忆,所以瞬间就可以判断,但对于100以内任意自然数,如何快速判断是否是质数呢?其实只要掌握正确的方法,不需要任何专门训练,都可以在3秒内判断出来。一、首先要明确...
  • 本蒟蒻来强答一发一个人人皆知的方法你只要知道质数的定义,就可以报出一个正确的 做法;当然是从 到 一个一个枚举,看看除了 和它本身之外还有没有其他质因数了!当然这个方法显然太慢了一点,想要快速判断 这种...
  • 在求最大公因数或最小公倍数时,能快速判断两数是否互质,对正确率和解题速度起决定作用。什么是互质数?公因数只有1两个数,叫做互质数。当然,我们可以用互质数定义去判断:分别求两个数因数,再找公因数。...
  • 判断一个数P是否的素数一般方法: 方法1:k从2开始,到n-1为止,判断P是否可以整除k 改进1:k到sqrt(P)为止 改进2:k从3开始且只考虑奇数 时间复杂度:O(P) 一个更快算法:Miller-Rabin算法 实现:在2-P-...
  • 【C语言】判断质数

    2017-04-09 20:13:27
    这里给出是一个更快速的方法。要判断一个数是否为素数,只要判断比它开根号后数小数能否把它整除。原因如下: 一个数N,它是根号N平方,那么如果它有其他约数话,假设为A,B(约数肯定要成对出现)...
  • 素数筛法,是一种快速“筛”出2~n之间所有素数的方法。朴素筛法叫埃氏筛(the Sieve ofEratosthenes,埃拉托色尼筛),它过程是这样:我们把2~n数按顺序写出来: 从前往后看,找到第一个未被划掉数,2,这...
  • 1.作用:快速判断单个数是否质数 2.原理: 介绍费马小定理:对于每一个素数p,都有ap−1≡1(modp) 但是不是对于每一个有ab−1≡1(modb)b都是素数 如果存在b满足上述规则,那么b有1/4几率为素数 ...
  • 我现在想知道1——1e8范围内有多少个素数(质数),有什么方法? 朴素法,对于每一个数n,我们判断是否是素数。 像这样: bool check(int curr) { int i; for(i = 2; i < sqrt(curr)+1; ++i) { ...
  • $Miller Rabin$总结

    2019-03-16 19:29:00
    这是一个很高效的判断质数的方法,可以在用\(O(logn)\) 的复杂度快速判断一个数是否是质数。它运用了费马小定理和二次探测定理这两个筛质数效率极高的方法。 费马小定理判质数: \(a^{p-1}\equiv1\mod p\) 这个定理...
  • Miller-rabbin算法

    2018-07-21 18:28:17
    这个算法用于快速判断一个数是否是质数。 那怎么判呢? 首先,既然要快速,我们就不能用朴素的O(n‾√)O(n)O(\sqrt n)的试除法。我们会联想到质数的一些性质: ap−1≡1(modp)(0&amp;lt;a&amp;lt;p)ap−1...
  • 实例032 判断用户输入月份季节 2.4 循环控制 实例033 使用while与自增运算符循环遍历数组 实例034 使用for循环输出杨辉三角 实例035 使用嵌套循环在控制台上输出九九乘法表 实例036 用while循环计算1+1/2!+1...
  • 实例032 判断用户输入月份季节 2.4 循环控制 实例033 使用while与自增运算符循环遍历数组 实例034 使用for循环输出杨辉三角 实例035 使用嵌套循环在控制台上输出九九乘法表 实例036 用while循环计算1+1/2!+1...
  • 实例032 判断用户输入月份季节 42 2.4 循环控制 43 实例033 使用while与自增运算符循环遍历 数组 43 实例034 使用for循环输出杨辉三角 43 实例035 使用嵌套循环在控制台上输出 九九乘法表 44 实例036 用while循环...
  • 实例032 判断用户输入月份季节 42 2.4 循环控制 43 实例033 使用while与自增运算符循环遍历 数组 43 实例034 使用for循环输出杨辉三角 43 实例035 使用嵌套循环在控制台上输出 九九乘法表 44 实例036 用while循环...
  • 031 判断字符串是否回文 032 通讯录输入输出 033 扑克牌结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件字符数 038 同时显示两个文件内容 039 简单文本...
  • 031 判断字符串是否回文 032 通讯录输入输出 033 扑克牌结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件字符数 038 同时显示两个文件内容 039 简单文本编辑器 ...
  • C语言实例解析精粹源代码

    热门讨论 2009-09-20 03:39:01
    031 判断字符串是否回文 032 通讯录输入输出 033 扑克牌结构表示 034 用“结构”统计学生成绩 035 报数游戏 036 模拟社会关系 037 统计文件字符数 038 同时显示两个文件内容 039 简单文本编辑器 ...
  • 判断一个数是否是奇数:if( n&1 ) 其中:n为奇数 // 奇数2进制末位为1,1与1进行与运算结果为1; 拓展: n>>=1 右移1位 除以2; n<<=1 左移1位 乘以2; 费马小定理 费马小定理:假如p是质数,且...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

判断是否是质数的快速方法