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

发表于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 1 分钟

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