Miller_Rabbin&&Pollard_Rho 学习笔记

佚名 6年前 (2019-04-16) 随笔 1767人围观抢沙发百度已收录

占坑，待填

I Intro

首先我们考虑这样一个问题

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

给定一个正整数$p(p<=1e8)$,请判断它是不是质数

妈妈我会试除法！

于是，我们枚举$ \sqrt p$ 以内的所有数，就可以非常轻松地得到一定正确的答案。

贴一小段代码

bool check(int n)
{
    if(n==1) return false;
    for(int i=2;i*i<=n;++i)
        if(!(n%i)) return false;
    return true;
}

$Extra$：给定$p(p<=1e5)$个正整数$p(p<=1e8)$,请判断它是不是质数

妈妈我会埃氏筛！

所谓筛法，就是利用了一条最最基本的原理：素数的倍数一定是合数，于是，我们便可以在一定数据范围之内来解决多次询问一个数是否为素数的问题

埃氏筛便是基于这个最简单的思想

时间复杂度约为$O(nlog_{2}n)$

再贴一小段代码

void prime()
{
    memset(isprime,0,sizeof isprime);
    for(int i=2;i<=n;i++)
        if(isprime[i]==0)
            for(int j=i+i;j<=n;j+=i)
                isprime[j]=1;
}

$Extra^{2}$:给定$p(p<=1e7)$个正整数$p(p<=1e8)$,请判断它们是不是质数

妈妈我有信仰，我能写出常数极为优秀的埃氏筛

这显然是不现实的，那可以怎样解决这个问题呢？

爸爸我会欧拉筛！

我们会发现，在用埃氏筛解决问题的时候，我们仍然进行了一些不必要的操作，比如$30$,在程序运行中我们用了$2,3,5$三个素数来证明其为合数，这显然是十分不合常理的。

所以我们考虑对其进行优化。

我们考虑，对于每一对$(i,prime[j])$, 显然$i*prime[j] $为合数，我们将其筛去

当
\[ i \quad mod \quad prime[j] =0 \]
就说明剩余的情况，我们会在以后考虑到，因为每一个合数都可以分解为一个合数（或一个质数）和一个质数的乘积，这样就可以避免重复考虑

再贴一小段代码

void prime()
{
    memset(isprime,0,sizeof isprime);
    for(int i=2;i<=n;i++)
    {
        if(isprime[i]==0)
            ++cnt,prime[t]=i;
        for(int j=1;j<=t&&i*prime[j]<=n;++j)
        {
            isprime[i*prime[j]]=1;
            if(!(i%prime[j])) break;
        }
    }
}

$Extra^{3}$:给定$p(p<=1e4)$个正整数$p(p<=1e16)$，请判断它们是不是质数

好像没辙了