精华内容
下载资源
问答
  • 素数判定Miller_Rabin 算法详解 上次说好的要把素数判定和大数分解(见另一篇博文)的快速随机化算法解决了,于是乎今天就来解决,不得不说理解起来真的有困难。我只能大概的将思路理一下,若有错漏还请担待。 ...

    素数判定Miller_Rabin  算法详解


    上次说好的要把素数判定和大数分解(见另一篇博文)的快速随机化算法解决了,于是乎今天就来解决,不得不说理解起来真的有困难。我只能大概的将思路理一下,若有错漏还请担待。
    转载自大佬的博客:点击打开链接
    首先相信有一些数学和编程经验的读者应该知道,最简单直观简单的素数判定方法就是试除法。对于判断数n是否是素数,我们从2开始一直到sqrt(n)。如果找到一个因子则判断n不是素数,否则是素数。代码如下:
    bool isPrime( long long n )
    {
    	for(long long i = 2; i*i <= n; i++)
    	{
    		if(n%i == 0) return false;
    	}
    	return true;
    }

    如果要找到成1~n的所有素数那么这个时间代价就变为O(n^2),很多时候是不可接受的。
    所以随着学习的深入,我们了解到了素数筛法,即从2开始,2的倍数肯定不是素数,再向右扫描,如果扫描到素数,则重复之前的过程,剔除之后的部分合数(准确的说是关于当前质数的倍数),如果扫描到合数则跳过(表示前面已经更新过这个数不是素数)。然后都扫描一遍即可把1~n的素数求解出来。这个算法的复杂度略高于O(n)。素数筛代码如下:
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    const int MAXN = 500000;
    
    bool isprime[MAXN];
    int prime[MAXN];
    int cnt = 0;//保存素数个数
    void getPrime()
    {
    	for(int i = 1; i < MAXN; i++)
    		isprime[i] = true; //先假设所有数是素数,后面逐个扫描更新
    	for(int i = 2; i < MAXN; i++) //扫一遍
    	{
    		if(!isprime[i]) continue; //如果不是素数,则不往后面更新
    		
    		prime[cnt++] = i;
    		for(int j = 2 * i; j < MAXN; j += i)
    			isprime[j] = false;
    	}
    }
    
    int main()
    {
    	getPrime();
    	for(int i = 0; i < cnt; i++)
    		cout << prime[i] << endl;
    }

    这个算法的不是质数的数不知删了一次,接下来的求素数的代码,对不是素数的数只删了一次。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    #define maxn  100005
    #define mod 9901
    int prime[maxn];
    bool unprime[maxn];
    void getprime()
    {
        int i,j,k = 0;
        for(i = 2; i <maxn; i++)
        {
            if(!unprime[i])
            {
                prime[k++] = i;
            }
            for(j = 0; j < k && prime[j]*i <maxn; j++)
            {
                unprime[prime[j] *i] = true;
                if(i % prime[j] == 0)
                {
                    break;
                }
            }
        }
    }
    int main()
    {
    	getprime();
    	for(int i=0;i<30;i++)
    		printf("%d ",prime[i]);
    	return 0;
    }
    

    ---------------------------------------------------------------------------------------------------------------------------------------------

    于是进入我们今天的主题,Miller_rabin算法,优势可以单独判断一个大数是否素数。缺点他是一个不保证正确的算法,我们只能通过多次执行算法让这个错误的概率很小,不过幸运的是通常来看它的错误概率可以小到忽略不计。


    Miller_rabin算法描述
    算法的理论基础:
    1. Fermat定理:若n是奇素数,a是任意正整数(1≤ a≤ n−1),则 a^(n-1) ≡ 1 mod n。
    2. 推演自Fermat定理(具体过程我没看懂,Orz), 如果n是一个奇素数,将n−1表示成(2^s)*d的形式,d是奇数,a与n是互素的任何随机整数,那么a^d ≡ 1 mod n或者对某个r (0 ≤ r≤ s−1, j∈Z) 等式a^((2^r)*d) ≡ −1 mod n 成立。



    聪明的读者已经发现上述的定理是一个数是素数的必要条件而非充分条件,所以这就是这个算法的不精确的原有,对于一些特定的检验算子a,存在一些合数也满足上述定理。所以我们要多找几个a反复检验,这样能让错误率大大降低。

    那么我们按照上述的定理2,首先重复n次实验。对于每一次实验,随机取检验算子a,带入定理2进行检验,看看在算子a下,n能否满足
    a^d ≡ 1 mod n或者对某个r(0 ≤ r≤ s−1, j∈Z) 等式a^((2^r)*d) ≡ −1 mod n       **
    如果任意一次实验不满足,则判定不是素数,如果都满足,可近似可以认为是素数(错误率极小)。

    代码实现如下:(代码中的q_mul和q_pow表示快速乘法和快速幂运算,具体讲解请参考另一篇博文)
    
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <map>
    using namespace std;
    
    const int times = 20;
    int number = 0;
    
    map<long long, int>m;
    long long Random( long long n )            //生成[ 0 , n ]的随机数
    {
        return ((double)rand( ) / RAND_MAX*n + 0.5);
    }
    
    long long q_mul( long long a, long long b, long long mod ) //快速计算 (a*b) % mod
    {
        long long ans = 0;
        while(b)
        {
            if(b & 1)
            {
                ans =(ans+ a)%mod;
            }
            b >>=1;
            a = (a + a) % mod;
    
        }
        return ans;
    }
    
    long long q_pow( long long a, long long b, long long mod ) //快速计算 (a^b) % mod
    {
        long long ans = 1;
        while(b)
        {
            if(b & 1)
            {
                ans = q_mul( ans, a, mod );
            }
            b >>= 1;
            a = q_mul( a, a, mod );
        }
        return ans;
    }
    
    
    bool witness( long long a, long long n )//miller_rabin算法的精华
    {//用检验算子a来检验n是不是素数
        long long d= n - 1;//n=(2^s)*d-1;
        int s= 0;
        while(d % 2 == 0)
        {
            d /= 2;
            s++;
        }
    
        long long x = q_pow( a, d, n ); //得到a^d mod n
        if(x == 1 || x == n - 1) return true;    //余数为1则为素数
        while(s--) //否则试验条件2看是否有满足的 s
        {
            x = q_mul( x, x, n );
            if(x == n - 1) return true;
        }
        return false;
    }
    bool miller_rabin( long long n )  //检验n是否是素数
    {
    
        if(n == 2)
            return true;
        if(n < 2 || n % 2 == 0)
            return false;                //如果是2则是素数,如果<2或者是>2的偶数则不是素数
    
        for(int i = 1; i <= times; i++)  //做times次随机检验
        {
            long long a = Random( n - 2 ) + 1; //得到随机检验算子 a
            if(!witness( a, n ))                        //用a检验n是否是素数
                return false;
        }
        return true;
    }
    
    
    int main( )
    {
        long long tar;
        while(cin >> tar)
        {
            if(miller_rabin( tar ))    //检验tar是不是素数
                cout << "Yes, Prime!" << endl;
            else
                cout << "No, not prime.." << endl;
        }
        return 0;
    }
    
    


    嗯,就是这样,至于那个定理我真的不是很清楚为何为这样,有一篇讲解文你们有兴趣的话看看吧。

    http://blog.csdn.net/fisher_jiang/article/details/986654

    展开全文
  • 素数判定

    2019-11-28 18:30:52
    素数判定 对于表达式n^2+n+41,当n在[x,y]范围内取整数值时,判定该表达式的值是否都为素数 若都为素数,输出OK,否则输出Sorry #include<iostream> using namespace std; //素数判定 //对于表达式n^2+n+41,当...
    • 素数判定
      对于表达式n^2+n+41,当n在[x,y]范围内取整数值时,判定该表达式的值是否都为素数
      若都为素数,输出OK,否则输出Sorry
    #include<iostream>
    
    using namespace std;
    //素数判定
    //对于表达式n^2+n+41,当n在[x,y]范围内取整数值时,判定该表达式的值是否都为素数
    //若都为素数,输出OK,否则输出Sorry
    int isPalind(int n) {
    	int a = (int)sqrt(n);
    	for (int i = 2; i <= a; i++) {
    		if (n % i == 0)
    			return 0;
    	}
    	return 1;
    }
    int main() {
    	int x, y;
    	bool flag;
    	cin >> x >> y;
    	if (x == 0&&y==0) {
    		return 0;
    	}
    	for (int i = x; i <= y; i++) {
    		if (isPalind(pow(i, 2) + i +41) == 1)
    			flag = 1;
    		else {
    			flag = 0;
    			break;
    		}
    	}
    	if (flag == 1) {
    		cout << "OK" << endl;
    	}
    	else {
    		cout << "Sorry" << endl;
    	}
    	return 0;
    }
    

    素数判定

    展开全文
  • 素数判断

    万次阅读 2017-11-30 12:59:13
    在Raptor的某些问题中,会有判断素数或者找出某一区间范围内的素数,这样的问题比较多,因此本篇内容讲解怎么判断一个数是不是素数 定义:质数(prime number)又称素数,质数定义为在大于1的自然数中,除了1和它...

    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

    展开全文
  • 素数定义 素数判定证明 素数求解算法 素数定义 素数判定证明 素数求解算法
  • 题目链接:素数判定 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 169265 Accepted Submission(s): 59989   Problem Description ...

    题目链接:素数判定

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
    Total Submission(s): 169265    Accepted Submission(s): 59989

     

    Problem Description

    对于表达式n^2+n+41,当n在(x,y)范围内取整数值时(包括x,y)(-39<=x<y<=50),判定该表达式的值是否都为素数。

     

    Input

    输入数据有多组,每组占一行,由两个整数x,y组成,当x=0,y=0时,表示输入结束,该行不做处理。

     

    Output

    对于每个给定范围内的取值,如果表达式的值都为素数,则输出"OK",否则请输出“Sorry”,每组输出占一行。

     

    Sample Input

    0 1 0 0

     

    Sample Output

    OK

     

    题记:

    构造判定一个数是否为素数的函数,以后再遇到素数判定问题可以直接把此函数copy来使用。

    判断采用的是试除法。

     

    素数判定函数:

    int isnotprime(int n)  
    {  
        if(n % 2 == 0)  
            return 1;  
      
        int end = sqrt(n), i;  
        for(i=3; i<=end; i+=2) {  
            if(n % i == 0)  
                break;  
        }  
      
        return i > end ? 0 : 1;  
    }  

    该题的C语言程序如下:

    /* HDU2012 素数判定 */  
      
    #include <stdio.h>  
    #include <math.h>  
      
    #define fun(n) n*n + n + 41  
      
    // 试除法判断一个整数是否为素数  
    int isnotprime(int n)  
    {  
        if(n % 2 == 0)  
            return 1;  
      
        int end = sqrt(n), i;  
        for(i=3; i<=end; i+=2) {  
            if(n % i == 0)  
                break;  
        }  
      
        return i > end ? 0 : 1;  
    }  
      
    int main(void)  
    {  
        int x, y, i;  
      
        while(scanf("%d%d", &x, &y) != EOF) {  
            
            if(x == 0 && y == 0)  
                break;  
      
            // 对x和y之间的数进行判定  
            for(i=x; i<=y; i++) {  
                if(isnotprime(fun(i)))  
                    break;  
            }  
      
            //输出结果  
            if(i > y)  
                printf("OK\n");  
            else  
                printf("Sorry\n");  
        }  
      
        return 0;  
    }

     

    展开全文
  • 素数判定算法的实现

    2020-09-04 05:31:45
    主要介绍了素数判定算法的实现,素数判定问题是一个非常常见的问题,本文介绍了常用的几种判定方法,需要的朋友可以参考下
  • 素数判定与大数分解

    2018-11-29 08:37:51
    素数判定与大数分解 [孙琦,旷京华 编著] 2014年版 素数判定与大数分解问题在数论中占有重要地位,远古时代人们就十分重视它的研究,近年来,由于计算机科学的发展,使这一古老的问题焕发了青春,形成了数论中的新...
  • HDU 2012 素数判定

    万次阅读 2019-10-18 21:00:16
    素数判定 Problem Description 对于表达式n^2+n+41,当n在(x,y)范围内取整数值时(包括x,y)(-39<=x<y<=50),判定该表达式的值是否都为素数。 Input 输入数据有多组,每组占一行,由两个整数x,y组成,当...
  • 素数判断1233

    2018-04-16 14:04:06
    简单的素数判断1

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,626
精华内容 28,250
关键字:

素数判定