求解某一范围内的全部素数

素数又称质数,是指大于1的自然数中,除了1和它本身,不能被其它自然数整除的数字。1被定义为非素数。大于1的自然数,如果不是素数则为合数2是最小的素数

问题:给定一个范围,求解这个范围内的全部素数。

一、试除法

基本思想:为了判断自然数x是否是素数,我们可以从2开始,分别除以不大于x的每个数,如果存在能整除x的数,则x不是素数。

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*判断一个数是否是素数*/
bool is_prime(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (n%i == 0)
{
return false;
}
}
return true;
}
/*方法一 试除法*/
void prime_number1(vector<int>& prime, unsigned long long n)
{
for (int i = 2; i <= n; i++)
{
if (is_prime(i))
{
prime.push_back(i);
}
}
}

时间复杂度:O(n*sqrt(n))

二、埃拉托斯特尼筛法

基本思想埃拉托斯特尼筛法(sieve of Eratosthenes ) 是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于 n 的所有素数,我们先找出 sqrt(n) 内的所有素数 p1, p2, p3, , , pk-1, pk,其中 k=floor(sqrt(n)) (floor表示向下取整),依次剔除 pi (1<=i<=k) 的倍数,剩下的所有数都是素数。下面我们来看一个来自维基百科的例子,如果求25内的所有素数

1.列出大于等于2小于等于25的所有数组成的序列:

  • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

2.去掉素数2的所有倍数:

  • 2 3 5 7 9 11 13 15 17 19 21 23 25

3.去掉素数3的所有倍数:

  • 2 3 5 7 11 13 17 19 23 25

4.去掉素数5的所有倍数:

  • 2 3 7 11 17 19 23

5.因为 5=sqrt(25) ,所以算法结束。剩下的所有数都是素数。

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*方法三 埃拉托斯特尼筛法*/
void prime_number3(vector<int>& prime, unsigned long long n)
{
vector<bool> is_prime(n + 1, true);
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
{
prime.push_back(i);
}
for (int j = i * i; j <= n; j += i)
{
is_prime[j] = false;
}
}
}

时间复杂度:O(nlogn)

三、欧拉筛法

基本思想:回顾上文的埃拉托斯特尼筛法,核心思想就是依次剔除素数的倍数。这里我们很容易就能想到此算法存在的缺点:对于两个素数的公倍数,我们可能会进行多次剔除。于是便出现了欧拉筛法,核心思想便是对于一个没被筛选过的数来说,它只需要被第一个整除它的素数筛掉就行。

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*方法四 欧拉筛法*/
void prime_number4(vector<int>& prime, unsigned long long n)
{
vector<bool> is_prime(n + 1, true);
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
{
prime.push_back(i);
}
for (int j = 0; j < prime.size() && i*prime[j] <= n; j++)
{
is_prime[i*prime[j]] = false;
if (i%prime[j] == 0)
{
break;
}
}
}
}

时间复杂度:O(n)

参考文章https://www.jianshu.com/p/7867517826e7

Author: wnxy
Link: https://wnxy.github.io/2021/06/27/Calculate_prime_numbers/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.