算法竞赛中的大素数问题和算法

本文讨论的背景是算法竞赛。

算法竞赛中最常用的筛素数算法是埃式筛法:

1
2
3
4
5
6
7
8
9
10
11
const int N = 1000010;
int vis[N], n, prime[N];

void init() {
n = 0;
memset(vis, 0, sizeof vis);
for (int i = 2; i <= 1000000; ++i) if (!vis[i]) {
prime[n++] = i;
for (int j = i + i; j <= 1000000; j += i) vis[j];
}
}

这个算法的时间复杂度还不错,要筛出 10^6 以内的素数,效率是能接受的;但要筛出 10^7 以内的素数就很吃力了,大部分情况下都会超时。

另外,这个算法的空间复杂度是O(n)(需要 vis 数组进行标记),要想筛出 10^8 或更大规模的素数时,内存会成为限制;因此,埃式算法看起来并不适合处理大素数相关的问题。

我们下面来讨论一点算法竞赛中和大素数相关的问题,首先我们定义什么是本文所指的大素数:算法竞赛中无法用埃式筛法筛出来的素数

例如,我们要判断 [1, 10^9] 中的某个数字 X 是否为素数,这属于大素数问题吗?不属于,因为只需要找出 sqrt(10^9) 以内的素数,逐一判断是否为 X 的素因子即可,筛选 sqrt(10^9) 以为的素数在埃式算法的能力范围内。

再比如,我们要判断 [1, 10^18] 中的某个数字 X 是否为素数 ,属于大素数问题吗?在本文的讨论范围内,是大素数问题,因为似乎要筛选出 sqrt(10^18) 以内的素数才能解决这个问题,这超过了埃式筛法的能力。

再比如,找出 [1, 2^31-1] 中的所有素数,属于大素数问题吗?当然属于,埃式算法办不到。

两种常用的大素数相关算法

使用 Miller Rabbin 测试算法判断一个数字是否为素数

  • 费马小定理:p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
  • 伪素数:n是正整数,且gcd(a,n)=1,且a^(n-1)≡1(mod n),称n是基于a的伪素数
  • 如果一个数字是伪素数,那它很可能是一个素数

算法描述:

  • 对于一个正整数 n,不断枚举 [1, n-1] 内的数字 a,假如都满足 a^(n-1)≡1(mod n),则判断 n 为质数

算法竞赛中的代码实现:

  • random [1, n-1] 中的数字,用快速幂取模计算出 (a^(n-1))%n 是否为1

筛出某个区间内的大素数(前提是这个区间的长度不大,例如在 10^6)

  • 例如筛出 [2^30, 2^30 +10^6] 内的素数,这个区间内的素数都是大素数,但这个区间的长度只有 10^6
  • 典型题目 POJ 2689 Prime Distance

算法描述:

  • 埃式筛法的延伸,二次筛法
  • 由于区间长度在可接受的访问内,因此把这个区间的合数都去掉,剩下的就是素数
  • 埃式筛法每次都会筛掉某个素数的倍数;因此找出小素数(例如 10^6 以内的素数),枚举小素数,然后筛掉区间内每个小素数的倍数

对于大素数问题,利用问题性质进行分析,而不是强行筛素数

我们有了 Miller Rabbin 测试算法后,要判断任何一个 int64 以内的数字是否为素数是没有问题的。

但是要找出 int64 里面的所有素数是不可取的,因为即使有最优的时间复杂度算法,单单要用数组将这些素数存起来都无法办到。

很多大素数问题,看上去似乎要筛出所有素数,实际上题目中都提供了很多限制条件,要善于利用这些条件,挖掘性质,避免陷入找出所有大素数的思维定势中

总结

  • 埃式筛法不仅能筛出小素数,很多大素数问题也可以通过埃式筛法的延伸解决
  • 使用 Miller Rabbin 测试算法判断一个数字是否为素数
  • 善于利用题目中的特殊条件,发掘性质
  • 避免陷入企图找出所有大素数的思维定势
坚持原创分享,您的支持将鼓励我继续创作!