求素数的方法完整归纳,学的不仅是“求素数”!

终遇你 5月前   阅读数 35 0

一、相关概念

定义:素数(Prime Number)又称质数,是指大于1且只能被1和它本身整除的正整数,例如2,3,5,7,11等。

与素数相对的就是合数,它能被一个本身之外的数整除,例如4,6,8,9等。注意:1既不是素数也不是合数

素数的分布很不均匀,下表部分列出了小于 x x 的素数个数函数 p i ( x ) p_i(x)

x p i ( x ) p_i(x)
10 4
100 25
1,000 168
10,000 1,229
100,000 9,592
1,000,000 78,498
10,000,000 664,579
100,000,000 5,761,455
1,000,000,000 50,847,534
10,000,000,000 455,052,511
100,000,000,000 4,118,054,813
1,000,000,000,000 37,607,912,018
10,000,000,000,000 346,065,536,839
100,000,000,000,000 3,204,941,750,802
1,000,000,000,000,000 29,844,570,422,669
10,000,000,000,000,000 279,238,341,033,925
100,000,000,000,000,000 2,623,577,157,654,233
1,000,000,000,000,000,000 24,739,954,287,740,860
10,000,000,000,000,000,000 234,057,667,276,344,607
100,000,000,000,000,000,000 2,220,819,602,560,918,840

二、素数的判定

方法1:
这种方法是基于素数的定义的判定,也是新手最容易想到的一种方法。只要正整数 n n 不能被区间 [ 2 , n ) [2,n) 中的整数整除,那么它满足素数的素数的定义,即 n n 是素数。(注意, 2 2 需要特判),算法的时间复杂度为 O ( n ) O(n)

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

方法2:
这个方法是对方法1的改进,我们知道如果一个数为合数,那么它可以分解为两个相等的数或者一小一大的两个数相乘。例如 16 16 可以表示为 2 8 2*8 ,也可以表示为 4 4 4*4 。所以我们

因此,我们只要正整数 n n 不能被区间 [ 2 , n ) [2, \sqrt{n}) 中的整数整除,就可以断定 n n 为素数,算法的时间复杂度就降到 O ( n ) O(\sqrt{n}) 。这种方法也是我们最常用的判断方法。

int isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}

需要注意的一点是,很多人因为贪图方便,喜欢把上面i <= sqrt(n)写成i*i <= n。这样虽然也没有错,但是如果要判定的数大于 2 31 1 \sqrt {2^{31}-1} 就会爆int,导致答案错误。


方法3:
这种方法名为Miller-Rabin素性测试,主要用于判定比较大的数(通常大于 1 0 9 10^9 )是否为素数,算法时间复杂度为 O ( t l o g n ) O(tlogn) (其中, t t 为测试次数),通常是在程序设计竞赛中出现,非竞赛选手可以不用掌握。

Miller-Rabin素性测试需要用到快速幂和费马小定理,这里就不做详细介绍,后面的博客也会写到。需要注意的是,Miller-Rabin素性测试检测出来的素数有可能能是非素数! n n 一次通过测试,则 n n 不是素数的概率为25%;如果通过 t t 次测试,则 n n 不是素数的概率为 1 4 t \frac{1}{4^t} 。因此,在保持效率的同时也需要兼顾正确率。

typedef long long ll;
/** * 快速幂函数 * a为底数,n为指数,mod为模数 */
ll quick_pow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n) {
        if (n & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}
/** * Miller_Rabin素性测试 */
int Miller_Rabin(ll n) {
    if (n == 2) return 1;
    //测试次数的选取需要适当
    for (int i = 0; i < 10; i++) {
    	//随机数a需要小于n
        ll a = rand() % (n - 2) + 2;
        //如果不满足费马小定理,则n不是素数
        if (quick_pow(a, n - 1, n) != 1) return 0;
    }
    return 1;
}

三、求素数

接下来将给出三种求一系列素数(素数表)的方法,三种方法各有优劣,下面以求1000以内的素数为例进行讲解。

方法1:
利用上面素数判定的方法2进行判定,将判定为素数的数存进素数表中,这种方法通常用在求比较小的素数的时候,时间复杂度 O ( n n ) O(n \sqrt{n})

#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
int cnt, prime[maxn];
/** * 素数的判定函数 */
int isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}
int main()
{
    for (int i = 2; i <= 1000; i++)
        if (isPrime(i)) prime[++cnt] = i;
    printf("%d\n", cnt); //输出素数个数
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}

优点:程序逻辑简单、容易理解,适合新手学习。
缺点:算法效率较低,如果要求前 1 0 5 10^5 个素数时,算法便无法在 1 s 1s 内完成。


方法2:
这种素数的筛选法称为Eratosthenes筛法(埃拉托斯特尼筛法,简称埃氏筛),算法的时间复杂度为 O ( n l o g n ) O(n\,logn) 。相对来说还是比较好理解的,下面我们以求 [ 1 , n ] [1,n] 中的素数为例进行讲解:

  • 我们就先把1,2,3,4,5,6,7,8,9,10,11,12,……,n-1,n 的在纸上先写出来。

  • 由于我们知道1既不是素数也不是合数,所以先把1给划掉。

  • 然后我们走到 2 2 ,发现 2 2 没被划掉,说明 2 2 是素数,于是我们在写的数中从 2 2 2*2 开始 2 2 的倍数全部划掉。接着我们走到下一个没有被划掉的数(素数) 3 3 ,我们同样将写的数中从 3 3 3*3 开始 3 3 的倍数全部划掉……

  • 以此类推,我们依次访问没有被划掉的数 i i ,得到我们要求的素数,同时将从 i i i*i 开始的 i i 倍数全部划掉,最后那些没有被划掉的数都是我们要求的素数!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int cnt, prime[maxn], isNotPrime[maxn];
/** * Eratosthenes筛法,求n以内的素数 */
int getPrime(int n) {
    isNotPrime[0] = 1;
    isNotPrime[1] = 1;
    for (ll i = 2; i <= n; i++)
        if (!isNotPrime[i]) {
            prime[++cnt] = i;
            //把i的倍数都标记为不是素数
            for (ll j = i * i; j <= n; j += i)
                isNotPrime[j] = 1;
        }
}

int main()
{
    getPrime(1000);
    printf("%d\n", cnt); //输出素数个数
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}

优点:相比方法1,这种方法的效率已经有了质的提升,而且也不会很难理解。

缺点:同一个合数有可能会被重复划去,例如 12 12 会被 i = 2 i = 2 i = 2 i = 2 时划去,影响效率。


方法3:
这中素数的筛选法叫做欧拉筛,因为该算法对于合数有且只会筛除一次,所以常将其称为线性筛,时间复杂度为 O ( n ) O(n)

算法的核心思想: 对于每一个数(无论素数,还是合数) i i 筛掉所有小于 i i 最小质因子的质数乘以 i i 的数。代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int cnt, prime[maxn], isNotPrime[maxn] = {1, 1};
/** * 线性筛素数 */
int getPrime(int n) {
    for (ll i = 2; i <= n; i++) {
        if (!isNotPrime[i]) prime[++cnt] = i;
        //关键处1
        for (ll j = 1; j <= cnt && i * prime[j] <= n; j++) {
            isNotPrime[i * prime[j]] = 1;
            //关键处2
            if (i % prime[j] == 0) break;
        }
    }
}
int main()
{
    getPrime(1000);
    printf("%d\n", cnt); //输出素数个数
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}

可能看了上面的代码很多人还是没有理解,不过没关系,我们还会继续讲解。

由上面代码的关键处1可以知道,相比埃氏筛,线性筛在处理筛除时,无论 i i 是素数还是合数都会参与筛除过程。(下面 p j p_j 即为代码中的 p r i m e [ j ] prime[j]

  • 如果 i i 是素数,本次筛掉的是 i p j i *p_j ,其中 p j p_j 是小于或等于 i i 的素数。
  • 如果 i i 是合数,本次筛掉的 i p j i *p_j 中, p j p_j 表示的是小于或等于 i i 的最小质因数的素数。关键处2保证的就是 p j p_j 不大于 i i 的最小质因数。

部分筛除过程如下表:

2x2
2x3 3x3
2x4
2x5 3x5 5x5
2x6
2x7 3x7 5x7 7x7
2x8
2x9 3x9
2x10
2x11 3x11 5x11 7x11 11x11

(还不懂可以参悟一下这个表~)

优缺点总结:

  • 线性筛没有冗余,不会重复筛除同一个数,时间复杂度为线性,是最快的一种素数筛法,也是打素数表的最佳选择。
  • 相比前面两种算法,这种算法没有那么容易理解,很多人都只是选择背模板。

参考资料

  1. Eratosthenes筛法(埃式筛法)时间复杂度分析
  2. 信息学奥赛之数学一本通
  3. 线性筛素数(欧拉筛)(主要学习了证明)

既然都看到就这里了,希望你可以做到以下三点哦:

  • 点赞,这是对作者辛苦写作的最低成本的鼓励。
  • 答应我,把它学会!(别扔进收藏夹吃灰)
  • 可以考虑关注一波,算法系列的文章会持续更新。
发布了61 篇原创文章 · 获赞 116 · 访问量 1万+

注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: