素数（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