质数

⬅ 返回

1、试除法

1.1、试除法（不加优化）

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i < n;i ++){ //这个很好理解，从最小的质数2开始枚举到n - 1
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}

1.2、试除法（sqrt优化）

sqrt这个函数运行很慢，每次执行时都要运算一遍，所以比较慢

#include<math.h>
bool is_prime(int n){
    if(n < 2) return false; 
    for(int i = 2;i <= sqrt(n);i ++){ //优化部分
        if(n % i == 0){ 
            return false; 
        }
    }
    return true; 
}

1.3、试除法（i∗i≤n）

与根号差不多，但当i的值即将超过int的范围时，平方值是巨大的，不推荐。

1.4、试除法（i≤n/i）y总模板

也是根号的原理

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i ++){ //优化内容
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

2、筛质数

2.1、埃筛法（朴素筛法）

思路：

代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N= 1000010;
 
int primes[N], cnt;
bool st[N];
 
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
 
int main()
{
    int n;
    cin >> n;
 
    get_primes(n);
 
    cout << cnt << endl;
 
    return 0;
}