素数的筛选

2023-09-28 16:49:34

一般筛选

bool isprime (int x){
    if (x < 2)  return false;
    for (int i = 2; i < x / i; i++)
        if(x%i==0)
            return false;
    return true;
}

埃拉托斯特尼筛法

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

埃氏筛简单实现

给出要筛数值的范围n，找出以内的素数。
先用2去筛，即把2留下，把2的倍数剔除掉；
再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉，不断重复下去......。
直到数组中最后一个数小于当前所标记的素数的平方

举个栗子

计算【0，25】之间的所有素数

列出2以后的序列：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），重复第2步：2，3，5，7，11，13，17，19，23，25
一直到序列最后一个数小于当前所标记素数的平方（此时25 > 2^2，继续筛选）
标记下一个素数（5），删除5的倍数后：2，3，5，7，11，13，17，19，23
此时23 < 5^2，跳出循环，当前序列即为所求

C++代码实现

#include<iostream>
using namespace std;

int main(){
    bool isprime[21];
    for(int i=0;i<=20;i++)isprime[i]=true;//先全部置为真
    isprime[0]=isprime[1]=false;//1 0 不是素数

    for(int i=2;i<=20;i++){//从2开始往后筛
        if(isprime[i])
            for (int j = 2 * i; j <= 20; j += i)
                isprime[j]=false;

        if(isprime[i])
            cout<<i<<" ";
    }
}

再举个栗子

AcWing 867.分解质因数

给定 nn 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1 ≤ n ≤ 100，
2 ≤ ai ≤ 2e9，

输入样例：

2
6
8

输出样例：

思路及代码实现

x 的质因子最多只包含一个大于根号x 的质数。如果有两个，这两个因子的乘积就会大于 x，矛盾。
i 从 2 遍历到根号x。用 x / i，如果余数为 0，则 i 是一个质因子。
s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 。
最后检查是否有大于根号x 的质因子，如果有，输出。

#include <iostream>
using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)//此处思想类似于埃氏筛
        {
            int s = 0;
            while (x % i == 0){
                x /= i;
                s++;
            }
            cout << i << ' ' << s << endl;
        }

    //n中最多只包含一个大于sqrt(n)的质因子
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;  cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
}

码农公寓