【欧拉计划第 7 题】第 10001 个素数 10001st prime

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)$ 即可。既然在左侧都找不到因数,那么右侧一定不存在咯

贴下实现的代码,帮助理解

1
2
3
4
5
6
7
bool is_prime(int num)
{
for (int i = 2; i <= sqrt(num); i++)
if (num % i == 0)
return false;
return true;
}

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* @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