目录

前言

一、质数是什么

二、易错点

三、试除法判断是否为质数

四、质数常考三大模型

五、真题练手

前言

距离蓝桥杯还有一个月，高效复习蓝桥杯知识，

质数相关的题目在蓝桥杯中经常出现。例如，2016年蓝桥杯省赛初赛第四题就是要求判断一个数是否为质数。此外，还有许多与素数相关的题目，如求一定范围内素数数量、素数和等等。因此，掌握质数的判断、筛法、求和等基本算法是参加蓝桥杯的必备技能之一。

提示：以下是本篇文章正文内容，下面案例可供参考

一、质数是什么

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

二、易错点

1、考试中最常考到的模型是也就是最简单的模型，判断一下什么是质数，大部分使用暴力枚举直接从2开始到这个数判断，但是往往这样面对数据比较大的时候容易出现超时，可以使用sqrt（n），但是每次枚举都要调用一下，最好的方法是

for(int i = 2;i <= n / i;i ++)

 2、其次还有一点1和2都不是质数，这俩个数要进行特判一下，防止出错误。

三、试除法判断是否为质数

以下代码常用来判断是否为质数

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

四、质数常考三大模型

1、判断是否为质数

例

解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

bool is_prime(int x)
{
    if(x < 2 ) return false;
    for(int i = 2;i <= x / i;i ++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}
int main()
{
    int n;
    cin >>n;
    while(n--)
    {
        int x;
        cin >> x;
        if(pd(x)) cout << "Yes" <<endl;
        else cout <<"No" <<endl;
        
    }
}

2、分解质因数

 解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
void divide(int n)
{
    for(int i = 2;i <= n/i;i ++)
    {
        if(n % i == 0)
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            cout << i << " " << s <<endl;
        }
    }
    if(n > 1) cout << n << " " << "1" <<endl;
    puts("");
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
    
}

3、筛选质数

 解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1000010;
int prime[N],cnt;
bool st[N];
void get_primes(int x)
{
    for(int i = 2;i <= x;i++)
    {
        if(!st[i])
        {
            prime[cnt] = i;
            cnt ++;
        }
       for(int j = i;j <= x;j += i) st[j] = true; // 所有有整除关系的都筛掉
    }
    
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

五、真题练手

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

我们知道第一个质数是 22、第二个质数是 33、第三个质数是 55……

请你计算第 20192019 个质数是多少？

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

解

#include <iostream>
using namespace std;
bool divide(int x)
{
  if(x < 2) return false;
  for(int i = 2;i <= x / i;i ++)
  {
     if(x % i == 0) return false;
  }
  return true;
}
int res;
int main()
{
  int i;
  for(i = 1;;i ++)
  {
    
    if(divide(i))
    {
       res ++;
    }
    if(res == 2019) break;
  }
  cout << i ;
  return 0;
}