工学1号馆

home

素数判定算法

Wu Yudong    November 29, 2016     Algorithm   691   

素数(prime number)又称质数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为素数。本文的代码部分采用C99

方法1:直接根据素数的概念进行判定

bool isPrime(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

方法2:改进的方法判定素数

除了2以外的偶数都不是素数,这样可以通过加入判断来减少一半的计算次数,除了这个之外,注意到下面的性质:

如果n不是素数, 则n有满足1 < d <= sqrt(n)的一个因子d。改进的素数判定算法如下:

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

方法3:用素数表判定素数

这种方法首先是构建素数表,然后直接判断

int plist[10000], pcount = 0;

int isPrime(int n)
{
    int i;
    // 如果n是2,3,5,7其中之一的倍数,排除
    if ((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7)))
        return 0;
    //接下来排除两个大于7的素数乘积所组成的合数
    for (i = 0; plist[i] * plist[i] <= n; i++)
        if (!(n % plist[i]))
            return 0;
    return n > 1;
}

void initprime(void)
{
    int i;
    for (plist[pcount++] = 2, i = 3; i < 50000; i++)
        if (isPrime(i))
            plist[pcount++] = i;
}

方法4:miller-rabin算法

这种素数算法是基于费马小定理的一个扩展,首先看看费马小定理

费马小定理:对于质数p和任意整数a,有ap ≡ a(mod p)(同余)。反之,若满足ap ≡ a(mod p),p也有很大概率为质数。 将两边同时约去一个a,则有ap-1 ≡ 1(mod p)

也即是说:假设我们要测试n是否为质数。我们可以随机选取一个数a,然后计算an-1 mod n,如果结果不为1,我们可以100%断定n不是质数。

否则我们再随机选取一个新的数a进行测试。如此反复多次,如果每次结果都是1,我们就能很大程度上认为n是质数。

该测试被称为Fermat测试。需要注意的是:Fermat测试不一定是准确的,有可能出现把合数误判为质数的情况。费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael数。

Carmichael数是非常少的,前3个Carmichael数是561、1105、1729。在1~100000000范围内的整数中,只有255个Carmichael数。

为此又有二次探测定理,以确保该数为素数:

Miller和Rabin在Fermat测试上,建立了Miller-Rabin质数测试算法。与Fermat测试相比,增加了一个二次探测定理:

如果p是奇素数,则 x2 ≡ 1(mod p)的解为 x ≡ 1 或 x ≡ p – 1(mod p)

如果an-1 ≡ 1 (mod n)成立,Miller-Rabin 算法不是立即找另一个 a 进行测试,而是看 n-1 是不是偶数。如果 n-1 是偶数,另u=(n-1)/2,并检查是否满足二次探测定理即au ≡ 1 或 au ≡ n – 1(mod n)。

举个例子,假设n=341,我们选取的a=2。则第一次测试时,2340 mod 341 = 1。由于340是偶数,因此我们检查2170,得到2170 mod 341=1,满足二次探测定理。同时由于170还是偶数,因此我们进一步检查285 mod 341=32。此时不满足二次探测定理,因此可以判定341不为质数。

将这两条定理合起来,也就是最常见的Miller-Rabin测试但一次MR测试仍然有一定的错误率。为了使我们的结果尽可能的正确,我们需要进行多次MR测试,这样可以把错误率降低。

#include <stdlib.h>
#ifdef WIN32
typedef __int64 i64;
#else
typedef long long i64;
#endif

//计算a^b mod n
int modular_exponent(int a, int b, int n)
{                                
    int ret;
    for (; b; b >>= 1, a = (int)((i64)a) * a % n)
        if (b & 1) //如果b为奇数
            ret = (int)((i64)ret) * a % n;
    return ret;
}

// Carmicheal 数: 561,41041,825265,321197185
// time = 10
int miller_rabin(int n, int time)
{
    //确定n是奇数,且为素数或者为大于7的若干素数的乘积
    if (n == 1 || (n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7)))
        return 0;
    while (time--)
        if (modular_exponent(((rand() & 0x7fff << 16) + rand() & 0x7fff + rand() & 0x7fff) % (n - 1) + 1, n - 1, n) != 1)
            return 0;
    return 1;
}

方法5:筛法求素数

先介绍一个简单的近似线性的筛法Eratosthenes筛法(埃拉托斯特尼筛法)

先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……;具体过程如下图所示:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define n 1000
bool isprime[n];

void get_prime1(void)
{
    int i, j;
    memset(isprime, true, sizeof(isprime));
    for (i = 2; i * i <= n; i++) {
        if(isprime[i]) {
            for(j = i * i; j <= n; j += i)
                isprime[j] = false;
        }
    }
}

这种算法效率较高但是有些数会被重复筛去,如12在i=2和i=3是都被筛去下面介绍一种每个合数只被筛一次的算法

改进的算法–Euler筛法:

void get_prime()
{
    int cnt = 0;
    for (int i = 2; i < N; i++) {
        if (!tag[i])
            p[cnt++] = i;
        for (int j = 0; j < cnt && p[j] * i < N; j++) {
            tag[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)