素数筛

素数又叫做质数，即除了1和其本身之外，不存在其他的因数。

最简单的一个判断是不是素数的方法，就是从2开始一直到该数-1 如果中途出现了一个数i 可以被该数整除，那么就说明这个数不是素数

程序也很简单只需要一个for循环就可以实现

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

View Code

这个算法的时间复杂度是O(n)　　时间太长了！

我们可以进一步的优化。

首先，我们先想想

一个合数，我们以它的合数我们以它的平方根(假设为x)为界限，它都可以表示成一个大于x和一个小于x的数乘积或者是 x*x 的形式

因此我们可以把循环的界限一直到x就可以了

bool prime(int x)
{
    if (x <= 1)
        return false;
    for (int i=2;i*i <= x;i++)
    {
        if (x % i == 0) // i*i可能会爆int
            return false;
    }
    return true;
}

View Code

这个算法的复杂度就是O(n√n) 　　速度比第一个算法速度快多了

以上的两种方法虽然很容易想到　　但是实在是太low了　　

这里讲一个埃筛算法　　以后遇到筛选素数的题目至少要会用埃筛吧！

埃筛的理论其实也很容易想到：就是如果我们已经找到了一个素数，那么这个素数的倍数肯定就不是素数

void is_prime()
{
    memset(prime,true, sizeof(prime));
    for (int i=2;i<N;i++)
    {
        if (prime[i])
        {
            for (int j=2*i;j<N;j+=i)
            {
                prime[j] = false;
            }
        }
    }
}

View Code

我们还可以改进一下

因为第一个for循环是为了找素数　　我们其实找到根号N 就可以了　因为假设m是素数(m < √N) 那么m * m (m * m > √N) 在第二个循环已经把它变成了false　

所以第一个循环可以变成 for (int i=2;i*i<N;i++)

埃筛的算法复杂度是 O(nloglogn)

既然已经讲到了埃筛，那干脆再介绍一个更牛逼的筛法——线性筛

bool prime[N];
int p[N],tot; // 存储素数

void is_prime() {
    memset(prime, true, sizeof(prime));
    for (int i = 2; i < N; i++) {
        if (prime[i]) {
            p[tot++] = i;
        }
        for (int j = 0; i * p[j] < N && j < tot; j++)
        {
            prime[i*p[j]] = false;
            if (i%p[j]==0)
                break;
        }
    }
}

View Code

这个代码中的 i%p[j] == 0 break;　　是为了确保每次筛选的都是最小的质因数。　　例如12 = 2x6 或者 3x4 ，但是因为有了这行代码我们确保12是被2筛选的

线性筛的算法复杂度是O(n)

根据埃筛的原理

(1) 我们可以用它来预处理每个数的质因数

 1 vector<int> prime_factor[N];
 2 
 3 void solve(){
 4     for (int i=2;i<N;i++){
 5         if (prime_factor[i].size() == 0){
 6             for (int j=i;j<N;j+=i){
 7                 prime_factor[j].push_back(i);
 8             }
 9         }
10     }
11 }

Ackerman

(2)我们可以用它来预处理每个数的因数 (这个其实和上面那个差不多)

1 vector<int> prime_factor[N];
2 
3 void solve(){
4     for (int i=2;i<N;i++){
5         for (int j=i;j<N;j+=i){
6             prime_factor[j].push_back(i);
7         }
8     }
9 }

Ackerman

(3)我们可以用它来预处理每个数的质因数分解

 1 vector<int> prime_factor[N];
 2 
 3 void solve(){
 4     for (int i=2;i<N;i++){
 5         if (prime_factor[i].size() == 0){
 6             for (int j=i;j<N;j+=i){
 7                 int temp = j;
 8                 while (temp % i == 0){
 9                     prime_factor[j].push_back(i);
10                     temp /= i;
11                 }
12             }
13         }
14     }
15 }