C++知识点总结(12)：筛素数（筛质数）

一、判断n是不是素数

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n <= 1) // 0和1都不是素数
    {
        cout << "No";
        return 0;
    }
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) // 能被整除，说明不是素数
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

二、找n以内所有的素数

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        bool flag = true;
        for (int j = 2; j * j <= i; j++)
        {
            if (i % j == 0)
            {
                flag = false;
            }
        }
        if (flag)
        {
            cout << i << " ";
        }
    }
    return 0;
}

三、素数筛法

方法

将合数都删掉，剩下的数字就是所有的素数。

过程

删 $2$ 、 $3$ ……的倍数。

注意

像 $4$ 、 $6$ 、 $8$ 这种合数，就不用删它们的倍数了。因为它一定会被比它小的数删掉，就没有必要了。

程序

#include <iostream>
#include <cmath>
using namespace std;

int main()
{ 
    int n;
    cin >> n;
    int isPrime[100005] = {};
    /* isPrime[]: 状态数组
	              0: 表示合数（被筛掉的）
	              1: 表示质数 */
    for (int i = 0; i <= n; i++)
    {
        isPrime[i] = 1; // 默认是质数 
    }
    
    // 筛素数
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (isPrime[i] == 1) // 是质数
        {
            for (int j = i * 2; j <= n; j += i) // 遍历i的倍数
            {
                isPrime[j] = 0; // 筛掉i的倍数j 
            }
        }
    }
    
    // 输出
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i] == 1)
        {
            cout << i << " ";
        }
    }
    return 0;
}

四、埃氏筛法

方法

就是上述代码的加工，从 $i$ 的 $i$ 倍开始筛可以提高效率。

程序

#include <iostream>
#include <cmath>
using namespace std;

int main()
{ 
    int n;
    cin >> n;
    int isPrime[100005] = {};
    /* isPrime[]: 状态数组
	              0: 表示合数（被筛掉的）
	              1: 表示质数 */
    for (int i = 0; i <= n; i++)
    {
        isPrime[i] = 1; // 默认是质数 
    }
    
    // 筛素数
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (isPrime[i] == 1) // 是质数
        {
            for (int j = i * i; j <= n; j += i) // 遍历i从i开始的所有倍数
            {
                isPrime[j] = 0; // 筛掉i的倍数j 
            }
        }
    }
    
    // 输出
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i] == 1)
        {
            cout << i << " ";
        }
    }
    return 0;
}

五、欧拉筛法

方法

筛2~n所有数的质数倍，直到它的最小质因子倍

程序

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int pos = 1; 
	int isPrime[100005] = {}; // 状态数组
	int prime[100005] = {}; // 质数表
	for (int i = 0; i <= n; i++)
	{
		isPrime[i] = 1;
	}
	
	// 筛素数
	for (int i = 2; i <= n; i++)
	{
		if (isPrime[i] == 1)
		{
			prime[pos++] = i; // 存入质数表 
		}
		for (int j = 1; j <= pos-1 && i * prime[j] <= n; j++)
		{
			isPrime[i * prime[j]] = 0;
			if (i % prime[j] == 0)
			{
				break;
			}
		}
	}
	
	// 输出
	for (int i = 2; i <= n; i++)
	{
		if (isPrime[i] == 1)
		{
			cout << i << " ";
		}
	}
	return 0;
}