质数算法总结

学习视频

艾尔尼筛法

朴素解法

2是质数，2的倍数全部都不是质数，把不是质数的数在地图中全部涂掉

这个做法的复杂度很高，是 $o(nlog(logN))$

1
2
3
4
5
6
7
8


bool isnp[MAXN]; // is not prime: 不是素数
void init(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (!isnp[i])
            for (int j = i * i; j <= n; j += i)
                isnp[j] = 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


#include <bits/stdc++.h>
using namespace std;
 
const long long maxn = 10000007 + 10;
const long long maxp = 700000;
int vis[maxn];    // i是合数vis为1，i是素数，vis为0
long long prime[maxp];
//筛选
void sieve(long long n){
    //取根号
    long long m = (long long)sqrt(n + 0.5);
    memset(vis, 0, sizeof(vis));
    vis[2] = 0;//地图
    for (long long i = 3; i <= m; i += 2) {
        if(!vis[i])
            for (long long j = i * i; j <= n; j += i)
                vis[j] = 1;
        if(i * i > n)
            break;
    }
}
 
long long gen(long long n){
    sieve(n);
    long long c = 1;
    prime[0] = 2;
    for (long long i = 3; i <= n; i += 2)
        if(!vis[i]) //被涂黑的不是质数
            prime[c++] = i;
    return c;
}
 
int main()
{
    long long n, c;
    cout << "刷素数到n：";
    cin >> n;
    c = gen(n);
    for (long long i = 0; i < c; i++)
        printf("%lld", prime[i]);
    cout << endl << c;
    return 0;
}

费马小定理优化【科普，不用它】

这个算法不用，只是做个科普

定理内容： $a^p-a$ 是 a 的倍数,即 $(a^p-a) \mod p=0$

`a=?`, `p=5`	1	2	3	4
$a^p-a$	0	30	240	1020
$\mod p$	0	0	0	0

例如: $$ 令 \space a=1\ P=5\ 可得到：\ (a^P-a) \mod P \= 0 \mod 5 \= 0 $$ 以上定理无用，因为有卡迈克尔数，比如 561

线性筛法

证明这是一个 $O(N)$ 的算法

i 的值	质数表	筛去的数
2	2	4
3	2, 3	6, 9
4	2, 3	8
5	2, 3, 5	10, 15, 25
6	2, 3, 5	12
7	2, 3, 5, 7	14, 21, 28, 35
$⋯ $	⋯	⋯
每个质数只被筛一次，复杂度变为 $O(n)$ ，可以AC。

参考博客

这个算法的时间复杂度是 $o(N)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


bool isnp[MAXN];//是否是合数
vector<int> primes; // 质数表
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i]) //如果不是合数
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;//越界就跳过
            isnp[p * i] = 1;//可以直接乘出的数是合数
            if (i % p == 0)
                break; //直接break，比如 x*p ==i , 前面可以直接用 x乘出来
        }
    }
}

参考洛谷的题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态，逐个删去
	isPrime[1] = 0;//1不是素数
	
	for(int i = 2; i <= n; i++)
	{
		if(isPrime[i])//没筛掉 
			Prime[++cnt] = i; //i成为下一个素数
			
		for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
		{
        	//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[i*Prime[j]] = 0;
            
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break; //重要步骤。见原理
		}
	}
}

int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	GetPrime(n);
	while (q--)
	{
		int k;
		scanf("%d", &k);
		printf("%d\n", Prime[k]);
	}
	return 0;
}

文章目录