Question:
https://projecteuler.net/problem=7
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?
思路可以参考 wikipedia - Sieve of Eratosthenes
Solution:
public static long nthPrimeNumber(int n) { long[] primes = new long[n]; primes[0] = 2; primes[1] = 3; primes[2] = 5; primes[3] = 7; primes[4] = 11; primes[5] = 13; int i = 6; for (long x = primes[i-1] + 2; i < n; x += 2) { if(isPrime(x, primes)) primes[i++] = x; } return primes[n - 1]; } private static boolean isPrime(long p, long[] primes) { long max = (long) Math.ceil(Math.sqrt(p)); for (long divisor : primes) { if (divisor > max) break; if (p % divisor == 0) return false; } return true; }
Reference:
http://codereview.stackexchange.com/questions/40673/what-is-the-10001st-prime-number
相关推荐
P = 1st large prime number Q = 2nd large prime number (sizes of P and Q should not differ too much!) E = Public Exponent (a random number which must fulfil: GCD(E, (P-1)*(Q-1))==1) N = Public ...
1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of Reciprocal Approximation 8. Young Tableau 9. 整数划分 10. ...
1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of Reciprocal Approximation 8. Young Tableau 9. 整数划分 10. ...
- 最大公约数(Greatest Common Divisor)、素数判断(Prime)、素数筛选(Sieve Prime)。 - 模逆元(Module Inverse)、扩展欧几里得算法(Extended Euclid)、同余方程(Modular Linear Equation)。 - 中国剩余定理(Chinese ...
library of the Intel Quartus® Prime software and may be configured to the required number of bits per symbols, symbols per pixel, symbols in sequence or parallel and pixels in parallel. The VIP Suite...
23. LCA-RMQ-ST(最近公共祖先 - Range Minimum/Maximum Query - Sparse Table) 24. LCA-Tarjan(最近公共祖先 - Tarjan算法) 25. 指数型母函数(用于处理大数据问题) 26. AC自动机(Aho-Corasick自动机) 27. ...
ST表 Sparse-Table 伸展树 Splay 博弈论SG函数 Sprague-Grundy 栈的基本操作 Stack 递推法求解无符号第一类斯特林数 Stirling-Number(Cycle,Unsigned,Recursion) 递推法求解第二类斯特林数 Stirling-Number...
1. Fibonacci Number:斐波那契数列,递推公式为F(n) = F(n-1) + F(n-2),在动态规划和递归问题中常见。 2. Lucas Number:卢卡斯数列,与斐波那契数列类似,但初始值不同。 3. Catalan Number:卡特兰数,在计数...
- **斐波那契数列 (Fibonacci Number)** - 定义:一个数列,其中每个数字是前两个数字的和。 - 公式:$F_n = F_{n-1} + F_{n-2}$,$F_0=0$,$F_1=1$。 - **卢卡斯数列 (Lucas Number)** - 定义:一个与斐波那契...
go程序设计语言 Contents Preface................................................................................................................................. xix PART 1—WHY LEARN GO—GETTING ...
The Way to Go,: A Thorough Introduction to the Go Programming Language 英文书籍,已Cross the wall,从Google获得书中源代码,分享一下。喜欢请购买正版。 目录如下: Contents Preface......................