`

10001st prime number

阅读更多

 

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

分享到:
评论

相关推荐

    RSATool2.exe

    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 ...

    上海交通大学ACM算法模板

    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. ...

    ACM 算法模板集

    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. ...

    ACM_算法模板集史上最完整收藏版223页pdf

    - 最大公约数(Greatest Common Divisor)、素数判断(Prime)、素数筛选(Sieve Prime)。 - 模逆元(Module Inverse)、扩展欧几里得算法(Extended Euclid)、同余方程(Modular Linear Equation)。 - 中国剩余定理(Chinese ...

    Quartus Video and Image Processing Suite User Guide

    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...

    ACM试题集和答案

    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...

    上海交通大学ACM算法模板gai.pdf

    1. Fibonacci Number:斐波那契数列,递推公式为F(n) = F(n-1) + F(n-2),在动态规划和递归问题中常见。 2. Lucas Number:卢卡斯数列,与斐波那契数列类似,但初始值不同。 3. Catalan Number:卡特兰数,在计数...

    ACM_算法模板集.pdf

    - **斐波那契数列 (Fibonacci Number)** - 定义:一个数列,其中每个数字是前两个数字的和。 - 公式:$F_n = F_{n-1} + F_{n-2}$,$F_0=0$,$F_1=1$。 - **卢卡斯数列 (Lucas Number)** - 定义:一个与斐波那契...

    The way to go

    go程序设计语言 Contents Preface................................................................................................................................. xix PART 1—WHY LEARN GO—GETTING ...

    [Go语言入门(含源码)] The Way to Go (with source code)

    The Way to Go,: A Thorough Introduction to the Go Programming Language 英文书籍,已Cross the wall,从Google获得书中源代码,分享一下。喜欢请购买正版。 目录如下: Contents Preface......................

Global site tag (gtag.js) - Google Analytics