题目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) 的，会更快。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int c[1000001], tot;
   
5. bool is[3000001];
   
6. 
   
7. int main() {
   
8.         for (int i = 2; tot <= 10001 && i <= 3000000; ++i) {
   
9.                 if (!is[i]) c[++tot] = i;
   
10.                 for (int j = 1; j <= tot && c[j] * i <= 3000000; ++j) {
    
11.                         is[c[j] * i] = 1;
    
12.                         if (i % c[j] == 0) break;
    
13.                 }
    
14.         }
    
15.         printf("%d\n", c[10001]);
    
16.     return 0;
    
17. }

复制代码

两者对比，欧拉筛做法比暴力判断快了 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

左右丶

我来学习学习