做网站是什么职位,大型行业门户网站开发,企业网络营销推广,建设的网站欧拉计划简介#xff0c;本系列希望以通俗易懂的语言、简洁的代码#xff0c;带大家体会数学与编程结合的魅力。
Problem 7#xff1a; 10001 10001 10001st primeBy
标签#xff1a;质数、质数筛法
原文#xff1a;By listing the first six prime numbers: 2 2 2, …欧拉计划简介本系列希望以通俗易懂的语言、简洁的代码带大家体会数学与编程结合的魅力。
Problem 7 10001 10001 10001st primeBy
标签质数、质数筛法
原文By listing the first six prime numbers: 2 2 2, 3 3 3, 5 5 5, 7 7 7, 11 11 11, and 13 13 13, we can see that the 6 6 6th prime is 13 13 13. What is the 10 001 10\ 001 10 001st prime number?
翻译前 6 6 6个质数分别是 2 2 2、 3 3 3、 5 5 5、 7 7 7、 11 11 11和 13 13 13。第 10 001 10\ 001 10 001个质数是多少
题解质数判定解法时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn )埃式筛法解法时间复杂度 O ( n l o g l o g n ) O(nloglogn) O(nloglogn)欧拉筛 O ( n ) O(n) O(n)。
下面展示一下三种解法的代码。
质数判定 代码
#include bits/stdc.h
using namespace std;bool check(int x) {if (x 1) return 0;for (int i 2; i * i x; i) {if (x % i 0) return 0;}return 1;
}int main() {int cnt 0, i 1;while (1) {if (check(i)) {cnt;if (cnt 10001) {cout i endl;return 0;}}i;}return 0;
}埃式筛法 代码
#include bits/stdc.h
using namespace std;const int N 2e5 10;
bool isPrime[N]; // 0是 1不是质数int main() {isPrime[0] isPrime[1] 1;for (int i 2; i N; i) {if (!isPrime[i]) {for (int j 2 * i; j N; j i) {isPrime[j] 1;}}}int cnt 0;for (int i 2; i N; i) {if (!isPrime[i]) {cnt;if (cnt 10001) {cout i endl;return 0;}}}return 0;
}欧拉筛法 代码
#include bits/stdc.h
using namespace std;const int N 2e5 10;
int prime[N];
bool isPrime[N]; // 0是 1不是质数int main() {isPrime[0] isPrime[1] 1;int cnt 1;for (int i 2; i N; i) {if (!isPrime[i]) prime[cnt] i;for (int j 1; j cnt i * prime[j] N; j) {// 将以prime[j]]为最小质因数的合数筛掉isPrime[i * prime[j]] 1;// 保证只筛到以prime[j]为最小质因数的数if (i % prime[j] 0) break;}}cout prime[10001];return 0;
}“Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics.”
“欧拉计划的存在是为了每个对数学感兴趣的人鼓励他们挑战他们并最终培养他们的能力与乐趣。”
