精华内容
下载资源
问答
  • 判断质数/素数——我知道的最快方法

    万次阅读 多人点赞 2017-12-01 20:23:32
    标准版:大部分人都知道比较快的方法判断从2到sqrt(n)是否存在其约数,时间复杂度O(sqrt(n)) 高配版:判断2之后,就可以判断从3到sqrt(n)之间奇数了,无需再判断之间偶数,时间复杂度O(sqrt(n)/2) 尊享...

    标准版:大部分人都知道的比较快的方法:判断从2到sqrt(n)是否存在其约数,时间复杂度O(sqrt(n))

    高配版:判断2之后,就可以判断从3到sqrt(n)之间的奇数了,无需再判断之间的偶数,时间复杂度O(sqrt(n)/2)

     

    尊享版:

    首先看一个关于质数分布的规律:大于等于5的质数一定和6的倍数相邻。例如5和7,11和13,17和19等等;

    证明:令x≥1,将大于等于5的自然数表示如下:

    ··· 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ···

    可以看到,不和6的倍数相邻的数为6x+2,6x+3,6x+4,由于2(3x+1),3(2x+1),2(3x+2),所以它们一定不是素数,再除去6x本身,显然,素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个数只判断2个,时间复杂度O(sqrt(n)/3)。

    在高配版和尊享版中,都是一个剪枝的思想,高配版中裁剪了不必要的偶数,尊享版中裁剪了不和6的倍数相邻的数,虽然都没有降低时间复杂度的阶数,但都一定程度上加快了判断的速度。

    在此给出尊享版C++代码:

     

    #include <iostream>
    #include <math.h>
    using namespace std;
    int isPrime(int n)
    {	//返回1表示判断为质数,0为非质数,在此没有进行输入异常检测
    	float n_sqrt;
    	if(n==2 || n==3) return 1;
    	if(n%6!=1 && n%6!=5) return 0;
    	n_sqrt=floor(sqrt((float)n));
    	for(int i=5;i<=n_sqrt;i+=6)
    	{
    	    if(n%(i)==0 | n%(i+2)==0) return 0;
    	}
            return 1;
    } 
    int main()
    {
    	int flag;
    	flag=isPrime(37);
    	cout<<flag<<endl;
    	return 0;
    }

     

    python 版代码参考:https://github.com/hichenway/UsefulCode/blob/master/isPrimeFunction.py

     

     

     

    展开全文
  • 判断质数 素数——我知道的最快方法.pdf
  • 标准版:大部分人都知道比较快的方法判断从 2 到 sqrt(n) 是否存在其约数,时间复杂度 O(sqrt(n)) 高配版:判断 2 之后,就可以判断从 3 到 sqrt(n) 之间奇数了,无需再判断之间偶数,时间复杂度 O(sqrt(n)...

    转载自:https://blog.csdn.net/songyunli1111/article/details/78690447

    标准版:大部分人都知道的比较快的方法:判断从 2 到 sqrt(n) 是否存在其约数,时间复杂度 O(sqrt(n))

    高配版:判断 2 之后,就可以判断从 3 到 sqrt(n) 之间的奇数了,无需再判断之间的偶数,时间复杂度 O(sqrt(n)/2)

    尊享版:

    首先看一个关于质数分布的规律:大于等于 5 的质数一定和 6 的倍数相邻。例如 5 和 7,11 和 13,17 和 19 等等;

    证明:令 x≥1,将大于等于 5 的自然数表示如下:

    ··· 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ···

    可以看到,不在 6 的倍数两侧,即 6x 两侧的数为 6x+2,6x+3,6x+4,由于2(3x+1),3(2x+1),2(3x+2),所以它们一定不是素数,再除去 6x 本身,显然,素数要出现只可能出现在 6x 的相邻两侧。因此在 5 到 sqrt(n) 中每 6 个数只判断 2 个,时间复杂度 O(sqrt(n)/3)。

    (有同学对这里的原理不理解的话,可以去参考我的另一篇原创《我理解的素数——约数求法》)

    在高配版和尊享版中,都是一个剪枝的思想,高配版中裁剪了不必要的偶数,尊享版中裁剪了不和 6 的倍数相邻的数,虽然都没有降低时间复杂度的阶数,但都一定程度上加快了判断的速度。

    在此给出尊享版 C++ 代码:

    #include <iostream>  
    #include <math.h>  
    using namespace std;  
    int isPrime(int n)  
    {   //返回1表示判断为质数,0为非质数,在此没有进行输入异常检测  
        float n_sqrt;  
        if(n==2 || n==3) return 1;  
        if(n%6!=1 && n%6!=5) return 0;  
        n_sqrt=floor(sqrt((float)n));  
        for(int i=5;i<=n_sqrt;i+=6)  
        {  
            if(n%(i)==0 | n%(i+2)==0) return 0;  
        }
        return 1;  
    }   
    int main()  
    {  
        int flag;  
        flag=isPrime(101);  
        cout<<flag<<endl;  
        return 0;  
    }  
    
    展开全文
  • 导入——素数定义 ...因为质数除了1和本身之外没有其他因数,所以判断n是否为质数,根据定义,直接从2到n-1逐个判断是否存在因数可以将n整除即可。 //c++代码 int n; cin>>n; for(int i=...

    导入——质数(素数)的定义

    质数 :指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
    分布规律: 以36N(N+1)为单位,随着N的增大,素数的个数以波浪形式渐渐增多。

    1)简单粗暴法

    因为质数除了1和本身之外没有其他因数,所以判断n是否为质数,根据定义,直接从2到n-1逐个判断是否存在因数可以将n整除即可。

    //完整版方法1 C++代码:
    //Zhang Fan
    //2019/1226/17:40
    #include "stdafx.h"
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    int main(){
    	int i,n;
    	cin>>n;
    	for(i=2;i<= n;i++){
    		if(n%i==0){		cout<<"no"; system("pause");return 0;}
    			else {		cout<<"yes";system("pause");return 0;}
    	}//for
    }
    

    2)优化开方

    上一个方法易于理解,可是效率很显著地低下。
    为什么这么说?因为我们在对一个数n进行因数分解时,得到的两个数一定是一个小于等于√n,一个大于等于√n 的。
    举个例子 : 6=1×6=2×3 ,√6≈2.45。
    这里不是想说6不是质数这个简单的知识,而是 因数2 和 因数3 分布在了√6的两侧。遍历过程从小到大,如果遍历到因数3那么一定遍历过因数2,而在碰到因数2的时候判断就停止了。
    所以,上述代码中并不需要遍历到n-1,遍历到 √n 即可。

    //完整版方法2 C++代码:
    //Zhang Fan
    //2019/1226/17:40
    #include "stdafx.h"
    #include <stdio.h>
    #include <iostream>
    #include <math.h>
    using namespace std;
    int main(){
    	int n;
    	cin>>n;
    	float tmp;
    	tmp=floor(sqrt((float)n));
         for(int i= 2; i <=tmp; i++){
    	        	if(n %i== 0){ cout<<"no";system("pause");
    	        			 return 0 ;}
    	        }//for
    	  //如果能走出for循环,证明n是素数
          cout<<"yes";system("pause");
          return 0 ;
    }
    

    3)继续优化

    方法2时间复杂度是O(sqrt(n)),已经比方法1的O(n)快了很多。那么还有没有更好的方法呢?
    这里要引入一个性质:质数总是等于 6x-1 或者 6x+1,其中 x 是自然数。

    证明:令x≥1,将大于等于5的自然数表示如下:
    		······ 6x-16x,6x+16x+26x+36x+46x+5,6(x+1),6(x+1)+1 ······
    我们从6x开始,逐一进行判断:
    	6x		肯定不是质数,是偶数,6x=6*x;
    	6x+1	不一定;
    	6x+2	肯定不是质数,是偶数,6x+2=2*(3x+1)6x+3	肯定不是质数,6x+3=3*(2x+1)6x+4	肯定不是质数,是偶数,6x+4=2*(3x+2)6x+5	不一定;
    

    所以,质数只可能出现在6x的相邻两侧(但在6的倍数相邻两侧并不是一定就是质数,如 35,所以需要进一步判断)。 ——第一次if判断
    既然如此,我们可以以 6 作为阶梯逐步增大到 √n,每次只判断6x-1和6x+1,来遍历所有可能的因数。 ——第二次if判断

    完整版方法3 代码:

    //完整版方法3 C++代码:
    //Zhang Fan
    //2019/1226/17:40
    #include "stdafx.h"
    #include <stdio.h>
    #include <iostream>
    #include <math.h>
    using namespace std;
    int main(){	
    	int n;
    	cin>>n;
    		if(n==2 || n==3)	{	cout<<"yes";system("pause");return 0; }
    		if(n%6!=1 && n%6!=5){//如果不在6x的左右两侧,直接可以判断不是质数
    								cout<<"no";	system("pause");return 0;}
    	float n_sqrt;
    	n_sqrt=floor(sqrt((float)n));
    		for(int i=5;i<=n_sqrt;i+=6){
    			if(n%(i)==0 | n%(i+2)==0) {	cout<<"no";
    										system("pause");
    										return 0;}
    			}//for
    	//能走到这里证明已经经过了所有检验,是一个合格的质数了
         cout<<"yes";system("pause");return 0; 
    }
    /*也有写做如下的,一样的想法,都是(左边 = 6x-1,右边 = (6x-1)+ 2)
             for(int i= 5;i <=tmp; i+=6 )
                  if(num %i== 0||num %(i+ 2)==0 )
    */
    

    因为每6个数中只需判断2个,理论上讲整体速度应该会是方法2的3倍

    注:如有不足欢迎指出,笔者一定虚心思考接受!

    展开全文
  • 前言: 今天搞了一天这个 蒙格马利 什么,我自己肯定是搞不定,参照了很多资料,...一开始我想的方法就是用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

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


     








    展开全文
  • 计算小于n的质数个数 方法总结

    万次阅读 2018-04-04 15:14:24
    背景:统计质数个数是很基础的问题了,但是在n非常... 暴力解法:直接挨个去看是不是质数,判断质数的方法就看是不是能够被1和自身之外的整数整除class Solution: def countPrimes(self, n): """ ...
  • 素数本身这个概念很简单,要找因子只有1和它本身数,简单求法就是1到根号n遍历判断因子 如果要遍历1到n话,复杂度是O(n3/2),处理小规模数据没问题,但是大规模就会比较慢。 当然如果只要判断一个数,那...
  • 文章目录写在开头的话判断是否为质数题目分析写在最后的话: 这里是一段防爬虫文本,请读者忽略。 本文原创首发于CSDN,作者IDYS ...请记住:实践是掌握知识的最快方法 如果你只是怀着看看的态度去快速浏览
  • 素数四种判断方法、实现及比较

    万次阅读 多人点赞 2019-05-26 11:52:40
    计算机或者相关专业,基本上大一新生开始学编程都会接触一个问题就是判断质数,下面分享几个判断方法,从普通到高效。 算法 1)直观判断法 直观的方法,根据定义,因为质数除了1和本身之外没有其他约数,所以...
  • ②WC的原因是因为判断质数的时候,时间超时了,没有找到一个很好的方法去更简便更的判断出来,所以要补充知识点 2.心得 ①要掌握分析题目的方法:对于此题,要筛选出质数回文数,所以自然就会先想到有两种办法,先...
  • 用java求一定范围内的质数

    千次阅读 2008-11-06 10:17:00
    用java求一定范围内的质数 除了2要特殊处理以外,所有质数都是奇数,给定一个奇数i,判断从3开始到它自身开方之间所有奇数是否能整除就行了,这是最快的方法。 for (int i = min; i int temp = (int) Math.sqrt...
  • 基础模板之求一个数质因数

    千次阅读 2015-09-06 13:13:07
    一个数一定会有质因数(除了1),一个数可以分解成多个质因数乘积,例如12=2*2*3,。 求n质因数的方法: 法一。因为质因数顾名思义,即是质数也是因数,那么...简单的方法是下面这种,求x质因数,保存在数组
  • leetcode——Count Primes

    2016-07-10 19:53:08
    题目: 输出小于n的质数的个数 方法一: 能不能快速判断一个数字n是不是质数呢?...显然3是最快的做法,因此我们在搜索到一个质数后要将其保存到数组后面,下次直接遍历质数数组来判断n是不是质数 c
  • 复杂度从n2n^2n2可以降为n(n)n\sqrt(n)n(​n),采用埃氏筛算法可以降为nlgnlgnnlgnlgnnlgnlgn, 如果更进一步还可以采用线性筛的方法最快可以达到nnn. --------------朴素做法------------在判断的时候只需要判断...
  • 优化素数表

    2013-10-13 17:25:00
    当然这不是最好最快的方法,占用空间也不小,不过这种方法简单易行,运行效率也不是太低——比起最普通用函数判断每个数那也是天壤之别了,所以还是非常常用。 有一处优化:筛选i倍数时,可以直接从i^2开始...
  • 那么,基于比较稳定排序方法中,最快的方法就是归并了,所以直接按照归并排序思路,将数组分解、合并、排序即可。但是需要注意是,在常规归并排序时候,如果前一个元素大于后一个元素,直接进行交换即可,...
  •  《Java开发实战1200例》分为I、II两卷共计1200个例子,包括了开发中各个方面常用实例,是目前市场上实例全面开发类图书;书中实例来源于多位工程师多年积累,具有很强实用性。 本书是第II卷,以开发...
  •  《Java开发实战1200例》分为I、II两卷共计1200个例子,包括了开发中各个方面常用实例,是目前市场上实例全面开发类图书;书中实例来源于多位工程师多年积累,具有很强实用性。 本书是第II卷,以开发...
  •  《Java开发实战1200例》分为I、II两卷共计1200个例子,包括了开发中各个方面常用实例,是目前市场上实例全面开发类图书;书中实例来源于多位工程师多年积累,具有很强实用性。 本书是第II卷,以开发...
  •  《Java开发实战1200例》分为I、II两卷共计1200个例子,包括了开发中各个方面常用实例,是目前市场上实例全面开发类图书;书中实例来源于多位工程师多年积累,具有很强实用性。 本书是第II卷,以开发...
  • 实例249 始终在桌面顶层显示窗体 11.2 设置窗体大小 实例250 设置窗体大小 实例251 根据桌面大小调整窗体大小 实例252 自定义最大化、最小化和关闭按钮 实例253 禁止改变窗体大小 11.3 设置窗体标题...
  • 实例249 始终在桌面顶层显示窗体 11.2 设置窗体大小 实例250 设置窗体大小 实例251 根据桌面大小调整窗体大小 实例252 自定义最大化、最小化和关闭按钮 实例253 禁止改变窗体大小 11.3 设置窗体标题...
  • 实例249 始终在桌面顶层显示窗体 11.2 设置窗体大小 实例250 设置窗体大小 实例251 根据桌面大小调整窗体大小 实例252 自定义最大化、最小化和关闭按钮 实例253 禁止改变窗体大小 11.3 设置窗体标题...
  • 实例249 始终在桌面顶层显示窗体 11.2 设置窗体大小 实例250 设置窗体大小 实例251 根据桌面大小调整窗体大小 实例252 自定义最大化、最小化和关闭按钮 实例253 禁止改变窗体大小 11.3 设置窗体标题...
  • 实例249 始终在桌面顶层显示窗体 11.2 设置窗体大小 实例250 设置窗体大小 实例251 根据桌面大小调整窗体大小 实例252 自定义最大化、最小化和关闭按钮 实例253 禁止改变窗体大小 11.3 设置窗体标题...
  • <p>HashMap 桶容量要求必须是 2 N 次幂(在较老版本是质数),因为对现代处理器来说,除法与求余数是操作。使用 2 整数次方长度散列表,可用掩码代替除法。因为 get() 是使用...
  • 14. VSAM(虚拟存储存取方法)文件优点是:动态地______,不需要文件进行______,并能较地______进行查找。【山东大学 2001 三、4 (2分)】 四、应用题 1. 文件【山东工业大学 1998 一、1-1(2分)】 2. 文件...
  • 3.6 例题:讨厌的青蛙(POJ 2812) 3.7 本章小结 3.8 练习题 习题3-1:数字三元组(POJ 4146) 习题3-2:质数的和与积(POJ 4138) 习题3-3:不定方程求解(POJ 4139) 习题3-4:砝码称重(POJ 4141) 习题3-5:垃圾炸弹(POJ ...

空空如也

空空如也

1 2
收藏数 31
精华内容 12
关键字:

判断质数的最快方法