素数又叫做质数,即除了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 }
Ackerman

 

这三个代码可以自己想想

该博客参考了https://www.cnblogs.com/linyujun/p/5198832.html