题目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 个质数是多少？
视频讲解：
https://www.bilibili.com/video/BV1Rj411Q7Ar/
思路解析及源码参考（C & Python）：
**** Hidden Message *****
本帖最后由 zhangjinxuan 于 2023-5-22 19:53 编辑
优化
我们可以使用算法——欧拉筛，直接筛出质数。
这样的做法是 O(N) 的，会更快。
#include <bits/stdc++.h>
using namespace std;
int c, tot;
bool is;
int main() {
for (int i = 2; tot <= 10001 && i <= 3000000; ++i) {
if (!is) c[++tot] = i;
for (int j = 1; j <= tot && c * i <= 3000000; ++j) {
is * i] = 1;
if (i % c == 0) break;
}
}
printf("%d\n", c);
return 0;
}
两者对比，欧拉筛做法比暴力判断快了 50 倍！ 正常循环判断素数并计数，计数10001时print并输出 1 11111 4545
good object , thanks 我来学习学习 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)
0
让我来康康优化版的答案 {:5_109:} 阿斯顿 1 1 源码 OK 我来学习学习
页:
[1]
2