素数

本文以“求小于等于n的素数之和”这个题目为引，讲一下求素数几种方法的思想。

1. 试除法

思路：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数(素数)。那么我只需要将自然数循环从2判断到它本身，如果没有被其他自然数整除，那么这个就是素数。

int sumOfPrime1(int n)
{
    int sum = 0;
    for (int i = 2; i <= n; ++i){
        int j = 2;
        for (; j < i; ++j)
        {
            if (i%j == 0)
                break;
        }
        if (j >= i)
            sum += i;
    }
    return sum;
}

2. 试除法(sqrt版本)

思路：在试除法的基础上优化。假设num为合数，因为任何一个合数都可以分解成两个整数的乘积，即num=x*y，因为x和y都大于sqrt(num)是不成立的，所以x和y中一定有一个是小于等于sqrt(num)，这样我们就得出一个理论：一个大于1的自然数num，从2到sqrt(num)中，不能被其他自然数整除的数叫做质数(素数)。

int sumOfPrime2(int n)
{
    int sum = 0;
    for (int i = 2; i <= n; ++i){
        int j = 2;
        for (; j <= sqrt(i); ++j)
        {
            if (i%j == 0)
                break;
        }
        if (j > sqrt(i))
            sum += i;
    }
    return sum;
}

3. 试除法(sqrt优化版本)

思路：在暴力法(sqrt版本)的基础上优化。因为比2大的偶数都是2的倍数，即合数，所以，除了2以外，所有的质数都是奇数,这样我们就可以直接把所有偶数忽略掉啦。

int sumOfPrime3(int n)
{
    int sum = 0;
    if (n > 1)
        sum = 2;
    for (int i = 3; i <= n; i += 2){
        int j = 3;
        for (; j <= sqrt(i); j += 2)
        {
            if (i%j == 0)
                break;
        }
        if (j > sqrt(i))
            sum += i;
    }
    return sum;
}

4. 埃氏筛法

思路：因为任意一个合数至少有一个质因数，所以从2开始，把所有素数的倍数标记起来，那么剩下的没有标记的就是素数。
简单模拟一下：
假设n=20
i=2 标记：4，6，8，10，12，14，16，18，20
i=3 标记：9，12，15，18
i=4 不处理（已经在i=2的时候标记为合数了）
i=5 i>sqrt(n)跳出循环
所以小于等于n的素数之和为2+3+5+7+11+13+17+19=77

int sumOfPrime4(int n)
{
    bool *isprime = new bool[n + 1]{};
    for (int i = 2; i <= sqrt(n); ++i)
    {
        if (isprime[i] == false){
            for (int j = i * i; j <= n; j += i)
            {
                isprime[j] = true;
            }
        }
    }
    int sum = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (isprime[i] == false)
            sum += i;
    }
    delete[] isprime;
    return sum;
}

5. 埃氏筛法(优化版本)

思路：在埃氏筛法的基础上，避免偶数的标记。
简单模拟一下：
假设n=20
i=3 标记：9，15，
i=5 i>sqrt(n)跳出循环
所以小于等于n的素数之和为3+5+7+11+13+17+19=75+2=77

int sumOfPrime5(int n)
{
    bool *isprime = new bool[n + 1]{};
    for (int i = 3; i <= sqrt(n); i += 2)
    {
        if (isprime[i] == false){
            for (int j = i * i; j <= n; j += i * 2)
            {
                isprime[j] = true;
            }
        }
    }
    int sum = 0;
    if (n > 1)
        sum = 2;
    for (int i = 3; i <= n; i += 2)
    {
        if (isprime[i] == false)
            sum += i;
    }
    delete[] isprime;
    return sum;
}

6. 欧拉筛法

把所有质数的倍数标记起来且只标记一次，那么剩下的没有标记的就是素数。
欧拉筛法和埃氏筛法的唯一区别就是：埃氏筛法在标记合数的时候，会有重复标记的情况，而欧拉筛法，在标记合数的时候，每次都使用最小的质因数去标记，避免了重复标记的情况，所以更快。

简单模拟一下：（因数即为i，质因数为prime[j]）
假设n=20
因数为2，质因数为2，标记合数4
因数为3，质因数为2，标记合数6;质因数为3，标记合数9
因数为4，质因数为2，标记合数8；4%2==0跳出内层循环
因数为5，质因数为2，标记合数10；质因数为3，标记合数15；质因数为5，5x5>n跳出内层循环
因数为6，质因数为2，标记合数12；6%2==0跳出内层循环
因数为7，质因数为2，标记合数14；质因数为3，7x3>n跳出内层循环
因数为8，质因数为2，标记合数16；8%2==0跳出内层循环
因数为9，质因数为2，标记合数18；质因数为3，9x3>n跳出内层循环
因数为10，质因数为2，标记合数20；质因数为3，10x3>n跳出内层循环
因数为11，质因数为2，11x2>n跳出内层循环
因数为12，质因数为2，12x2>n跳出内层循环
因数为13，质因数为2，13x2>n跳出内层循环
因数为14，质因数为2，14x2>n跳出内层循环
因数为15，质因数为2，15x2>n跳出内层循环
因数为16，质因数为2，16x2>n跳出内层循环
因数为17，质因数为2，17x2>n跳出内层循环
因数为18，质因数为2，18x2>n跳出内层循环
因数为19，质因数为2，19x2>n跳出内层循环
因数为20，质因数为2，20x2>n跳出内层循环
因数为21，21>n跳出外层循环
所以小于等于n的素数之和为2+3+5+7+11+13+17+19=77

int sumOfPrime6(int n)
{
    int sum = 0;
    int count = 0;
    int *prime = new int[n + 1]{};
    bool *isprime = new bool[n + 1]{};
    for (int i = 2; i <= n; ++i)
    {
        if (isprime[i] == false){//保存质数
            sum += i;
            prime[count++] = i;
        }
        for (int j = 0; j < count&&i*prime[j] <= n; ++j)
        {
            isprime[i*prime[j]] = true;
            if (i%prime[j] == 0)//这句的作用就是要确定prime[j]是最小的质因数
                break;
        }
    }
    delete[] prime;
    delete[] isprime;
    return sum;
}

7. 欧拉筛法(优化版本)

思路：在欧拉筛法的基础上，避免偶数的判断。
**

int sumOfPrime7(int n)
{
    int sum = 0;
    int count = 0;
    int *prime = new int[n + 1]{};
    bool *isprime = new bool[n + 1]{};
    if (n > 1){
        prime[count++] = 2;
        sum = 2;
    }
    for (int i = 3; i <= n; i += 2)
    {
        if (isprime[i] == false){
            sum += i;
            prime[count++] = i;
        }
        for (int j = 1; j < count&&i*prime[j] <= n; ++j)
        {
            isprime[i*prime[j]] = true;
            if (i%prime[j] == 0)
                break;
        }
    }
    delete[] prime;
    delete[] isprime;
    return sum;
}

对于两种筛法空间的优化：可以用1位来标记1个合数，合数为1，素数为0，这样一个字节可以标记8个数字，相比使用bool类型来标记可以节省8倍的内存空间。

定义位域
struct S_Prime{
unsigned int a:1;
};
S_Prime prime[100];

如有不同的见解，可以在评论区留言，一起探讨，共同进步。