C++中的筛选质数的几种方法_c++找质数

一.暴力枚举法

int prime(int n)
{
    if (n == 1) return 0;
    for(int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) return 0;
    }
    return 1;
}
1
2
3
4
5
6
7
8
9

  这种算法完全是根据质数的定义来计算，比较容易理解，但时间复杂度比较高。

二.埃氏筛选法

bool prime[100000];       //长度可以改变
memset(prime, 1, sizeof(prime));  //埃筛一定要初始化数组值
prime[0] = 0;
prime[1] = 0;
for(int i = 2; i < 100000; i++)
{
    if (prime[i])
    {
        for(int j = i * 2; j < 100000; j += i)
        {
            prime[j] = 0;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  可以看出，埃式筛法还不错，时间复杂度降低了很多，但是也做了一些无用功，某个数字会被筛选多次，比如12这个数字，在2和3的时候就筛选了两次。既然有可优化的地方，那必然有更好的算法

三.欧拉筛选法

const int max = 1e7;//定义空间大小，1e7大约10MB
int prime[max + 1];//存放素数
bool visit[max + 1];//true表示被筛掉，表示素数
int prime()
{
    int get = 0;
    memset(v, 0, sizeof(v));
    v[0] = v[1] = 1;
    for (int i = 2; i <= max; i++)
    {
        if (!v[i])
            prime[get++] = i;
        for (int j = 0; j < get && i * prime[j] <= max; j++)
        {
            v[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
    return get;
}

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

  原理：由于所有合数都有一个最小质因子，所以在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。该算法的时间复杂度最低。