题目7：找出第10001个质数

欧拉计划

题目7：找出第10001个质数

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 10001st prime number?

题目翻译：

前六个质数是 2, 3, 5, 7, 11 和 13，其中第 6 个质数是 13。

那么第 10001 个质数是多少？


视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

zhangjinxuan

优化

我们可以使用算法——欧拉筛，直接筛出质数。

这样的做法是 O(N) 的，会更快。

#include <bits/stdc++.h>
using namespace std;

int c[1000001], tot;
bool is[3000001];

int main() {
        for (int i = 2; tot <= 10001 && i <= 3000000; ++i) {
                if (!is[i]) c[++tot] = i;
                for (int j = 1; j <= tot && c[j] * i <= 3000000; ++j) {
                        is[c[j] * i] = 1;
                        if (i % c[j] == 0) break;
                }
        }
        printf("%d\n", c[10001]);
    return 0;
}

两者对比，欧拉筛做法比暴力判断快了 50 倍！

PetalWill

正常循环判断素数并计数，计数10001时print并输出

迷白

1

a8634944

11111

whovian133

4545

auend

good object , thanks

siazb8590

我来学习学习

YZSNB

111

猫熊同学

import math

def isPrime(n):
    for i in range(2, math.isqrt(n)+1):
        if n % i == 0:
            return False
    return True

i = 1
n = 0
while True:
    i += 1
    if isPrime(i):
        # print(i)
        n += 1
    if n == 10001:
        print(i)
        break

# 答案是104743

歌者文明清理员

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

count = 0
i = 2
while count < 10001:
    if isprime(i):
        count += 1
    i += 1
print(i - 1)

pixie99

0

傲然子

让我来康康优化版的答案

gurite

不是黄瓜是傻瓜

阿斯顿

sfqxx

1

liangxixin

1

奋斗中的鱼

源码

nkysp

OK

左右丶

我来学习学习