Problem 7 10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?
问题 7 第 10001 个素数
通过列出前六个素数：2、3、5、7、11 和 13，我们可以看到第 6 个素数是 13。 第10001个质数是多少？
思路分析
读完题目，发现题目还是比较容易的。枚举出范围内所有的素数，加入循环判断，等到判断条件是第 100001 个质数时输出就好
质数
另外需要知道质数的概念
质数（又称素数），指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数
下面介绍一种比较容易理解的，在程序中判断数字是否为质数的方法
因为，一个数如果可以进行因数分解，那么分解后，得到的两个数一定是一个小于等于 sqrt(n) ，一个大于等于 sqrt(n) 所以，我们并不需要从 2 一直判断到 n-1 ，而只需遍历到 sqrt(n) 即可。既然在左侧都找不到因数，那么右侧一定不存在咯
贴下实现的代码，帮助理解
代码语言：javascript复制bool is_prime(int num)
{
for (int i = 2; i <= sqrt(num); i )
if (num % i == 0)
return false;
return true;
}代码实现
代码语言：javascript复制/*
* @Author: coder-jason
* @Date: 2022-04-13 16:25:25
* @LastEditTime: 2022-04-13 16:53:03
*/
#include <bits/stdc .h>
using namespace std;
int flag = 0; // 标记当前是第几个素数
bool is_prime(long long num)
{
for (long long i = 2; i <= sqrt(num); i )
if (num % i == 0)
return false;
return true;
}
int main()
{
long long i; // 注意考虑数据范围大小
for (i = 2; flag < 10001; i )
if (is_prime(i)) // 只有该数是素数,标记才自增 1
flag ;
cout << i << endl;
return 0;
}答案：104743
