计算并打印第n个素数
我正在尝试计算素数，我已经完成了。 但我想计算和打印第n个素数（用户输入），在计算其余部分（它们不会被打印）时，只打印第n个素数。
这是我到目前为止所写的内容：
import java.util.Scanner; /** * Calculates the nth prime number * @author {Zyst} */ public class Prime { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n, i = 2, x = 2; System.out.printf("This program calculates the nth Prime number\n"); System.out.printf("Please enter the nth prime number you want to find: "); n = input.nextInt(); for(i = 2, x = 2; i <= n; i++) { for(x = 2; x < i; x++) { if(i % x == 0) { break; } } if(x == i) { System.out.printf("\n%d is prime", x); } } } } 这是我编写的计算从1到n的素数的程序。 但是，我希望它只打印第n个素数，
我想到的是每次找到素数时都会对它进行某种计算和计算，当计数== n然后它打印出那个数字，但是我无法弄清楚如何降落它。
为了计算第n个素数，我知道两个主要变体。
直截了当的方式
这是为了计算从2开始的所有素数，直到达到期望的n th为止。
这可以通过不同的复杂程度和效率来完成，并且有两种概念上不同的方法。 首先是
按顺序测试所有数字的素数
这可以通过类似的驱动程序function来实现
public static int nthPrime(int n) { int candidate, count; for(candidate = 2, count = 0; count < n; ++candidate) { if (isPrime(candidate)) { ++count; } } // The candidate has been incremented once after the count reached n return candidate-1; }
确定效率的有趣部分是isPrime函数。
对于素数检查来说，显而易见的方法是，如果将素数定义为大于1且只能被1整除的数，并且我们在学校中学到了¹，则是
审判分庭
将定义直接转换为代码是
private static boolean isPrime(int n) { for(int i = 2; i < n; ++i) { if (n % i == 0) { // We are naive, but not stupid, if // the number has a divisor other // than 1 or itself, we return immediately. return false; } } return true; }
但是，正如你很快就会发现，如果你尝试它，它的简单性伴随着缓慢。 通过该素数测试，你可以在几毫秒内找到第1000 个素数，7919，在我的计算机上约为20，但找到10000 个素数，104729，需要几秒钟（~2.4秒），第100000 个素数，1299709几分钟（约5分钟），百万分之一，15485863分，大约需要八个半小时，第一百万分之一，179424673分钟，等等。 运行时复杂度比二次 - Θ（n²* log n）差。
所以我们想在某种程度上加快素数测试。 许多人采取的步骤是认识到n的除数（除了n本身）最多可以是n/2 。 如果我们使用这个事实并让试验分割循环只运行到n/2而不是n-1 ，那么算法的运行时间如何变化？ 对于复合数字，较低的循环限制不会改变任何内容。 对于素数，试验分割的数量减少了一半，因此整体而言，运行时间应该减少一个小于2的因子。如果你尝试一下，你会发现运行时间几乎完全减半，所以几乎所有的尽管有更多的复合材料而不是素数，但是花费时间来validation素数的素数。
现在，如果我们想要找到第十亿个素数，这没有多大帮助，所以我们必须做得更好。 尝试进一步减少循环限制，让我们看看实际需要n/2的上限是多少。 如果n/2是n/2的除数，则n/2是整数，换句话说， n可以被2整除。但是循环不会超过2，所以它永远不会（除了n = 4 ）到达n/2 。 快乐，那么n的下一个最大可能除数是什么？ 为什么，当然不是n/3 。 但是如果它是一个整数，则n/3只能是n的除数，换句话说，如果n可以被3整除，那么循环将在3（或之前，2）处退出并且永远不会达到n/3 （除了n/3因为n = 9 ）。 下一个可能的除数......
等一下！ 我们有2 <-> n/2和3 <-> n/3 。 n的除数成对出现。
如果我们考虑(d, n/d)的相应除数的对(d, n/d) ，则d = n/d ，即d = √n ，或者其中之一，例如d ，小于另一个。 但是d*d < d*(n/d) = n且d < √n 。 n对的每对相应除数包含（至少）一个不超过√n除数。
如果 n 是复合的，则其最小的非平凡除数不超过 √n 。
因此我们可以将循环限制减少到√n ，这会降低算法的运行时复杂性。 它现在应该是Θ（n 1.5 *√（log n）），但根据经验，它看起来好一点 - 但是，没有足够的数据可以从实证结果中得出可靠的结论。
它在大约16秒内找到了百万分之一的素数，在不到9分钟内找到了第一百万分之一，并且在大约四个半小时内找到了十亿分之一。 这仍然是缓慢的，但与十年左右相比，它将需要天真的试验部门。
由于存在素数的平方和两个接近素数的乘积，如323 = 17 * 19，我们不能将试验除法循环的限制降低到√n以下。 因此，在试用分区的同时，我们必须寻找其他方法来改进算法。
一个容易看到的事情是，除了2之外没有其他素数是偶数，所以我们只需要在处理完2之后检查奇数。但是，这并没有太大的区别，因为偶数是最便宜的复合 - 大部分时间仍用于validation素数的素数。 但是，如果我们将偶数作为候选除数看，我们看到如果n可以被偶数除尽，那么n本身必须是偶数，所以（除了2）它将在除以任何偶数之前被识别为复合尝试超过2。 因此，算法中出现的偶数大于2的所有除法必须留下非零余数。 因此，我们可以省略这些划分并仅检查2的可分性和从3到√n的奇数。 这将（确切地说）将数字确定为素数或复合数所需的除法数减半（因此不是确切地说），因此也就是运行时间。 这是一个好的开始，但我们能做得更好吗？
另一个大的数字族是3的倍数。我们执行的每第三个除法是3的倍数，但如果n可以被其中一个除尽，它也可以被3整除，因此没有除以9,15,21 ，...我们在算法中执行的将剩下0。那么，我们如何跳过这些划分呢？ 那么，2和3都不能分割的数字正好是6*k ± 1forms的数字。 从5开始（因为我们只对大于1的数字感兴趣），它们是5,7,11,13,17,19 ......，从1到下一个的步骤在2到4之间交替，这是很容易，所以我们可以使用
private static boolean isPrime(int n) { if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; int step = 4, m = (int)Math.sqrt(n) + 1; for(int i = 5; i < m; step = 6-step, i += step) { if (n % i == 0) { return false; } } return true; }
这给了我们另一个加速因子（接近）1.5，所以我们需要大约一个半小时到第一亿个素数。
如果我们继续这条路线，下一步就是消除5的倍数。互数为2,3和5的数字是表格的数字
30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29
所以我们每30个数字（加上三个最小的素数）只需要除以8。 从一个到下一个的步骤，从7开始，循环到4,2,4,2,4,6,2,6。这仍然很容易实现并产生另一个加速因子1.25（减去一点更复杂的代码）。 更进一步，7的倍数将被消除，每210个数字中有48个除以，然后是11（480/2310），13（5760/30030），依此类推。 消除其倍数的每个素数p产生（几乎） p/(p-1)的加速，因此返回减少而成本（代码复杂度，步骤的查找表的空间）随着每个素数而增加。
一般来说，在消除了六或七个素数（甚至更少）的倍数后，人们会很快停止。 然而，在这里，我们可以追溯到最后，当所有素数的倍数被消除并且只有素数被留作候选除数时。 由于我们按顺序查找所有素数，因此每个素数在需要作为候选除数之前找到，然后可以存储以备将来使用。 这会将算法复杂度降低到 - 如果我没有计算错误 - O（n 1.5 /√（log n））。 以存储质数的空间使用为代价。
通过试验划分，即得到它的好处，你必须尝试将所有素数除以√n或第一个除以n来确定n的素数。 在这里发现了大约一个半小时的第一亿次素数。
那怎么样
快速素性测试
与不存在复合数通常不具有的非平凡除数相比，素数具有其他数论性质。 如果这些属性快速检查，则可以形成概率或确定性素性测试的基础。 典型的这种财产与皮埃尔德费马的名字有关，他在17世纪初发现了
如果
p是素数，则p是所有a的（a p -a）的除数。
这个 - 费马的所谓“小定理” - 在等效公式中
设
p是素数，不能被p整除。 然后p除p-1 - 1。
大多数普遍的快速素性测试（例如Miller-Rabin）的基础以及更多的变体或类似物（例如Lucas-Selfridge）。
因此，如果我们想要知道一个不太小的奇数n是否是素数（偶数和小数被试验分割有效处理），我们可以选择任何数字a （> 1），它不是n的倍数，例如2，并检查n是否除n-1 - 1.由于n-1变大，通过检查是否a^(n-1) ≡ 1 (mod n) ，即通过模幂运算最有效地完成。 如果这种一致性不成立，我们就知道n是复合的。 然而，如果它成立，我们不能断定n是素数，例如2^340 ≡ 1 (mod 341) ，但341 = 11 * 31是复合的。 复合数n使得a^(n-1) ≡ 1 (mod n)被称为基数a费马伪a 。
但这种情况很少发生。 给定任何基数a > 1 ，尽管有一个无限数量的费马伪像基于a ，它们比实际质数少得多。 例如，只有78个base-2 Fermat pseudoprimes和76个base-3 Fermat pseudoprimes低于100000，但是9592个primes。 因此，如果选择任意奇数n > 1且任意基数a > 1并且找到a^(n-1) ≡ 1 (mod n) ，则n很可能实际为素数。
但是，我们处于稍微不同的情况，我们给n并且只能选择a 。 那么，对于奇数复合n ，对于多少a ， 1 < a < n-1可以a^(n-1) ≡ 1 (mod n)成立？ 不幸的是，有一些复合数字 - 卡迈克尔数 - 这样一致性就可以得到n 每 a互质。 这意味着要将Carmichael数与Fermat检验结合起来，我们必须选择一个n的主要除数之一的倍数 - 可能没有很多这样的倍数。
但我们可以加强Fermat测试，以便更可靠地检测复合材料。 如果p是奇素数，则写p-1 = 2*m 。 然后，如果0 < a < p ，
a^(p-1) - 1 = (a^m + 1) * (a^m - 1)
并且p恰好分为两个因子中的一个（两个因子相差2，因此它们的最大公约数是1或2）。 如果m是偶数，我们可以以相同的方式分割a^m - 1 。 继续，如果p-1 = 2^s * k且k odd，则写入
a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1)
然后p正好划分其中一个因素。 这引起了强大的费马测试，
设n > 2为奇数。 用k odd写n-1 = 2^s * k 。 给定1 < a < n-1 ，如果
-
a^k ≡ 1 (mod n)或 - 对于
0 <= j < s任何j，a^((2^j)*k) ≡ -1 (mod n)
那么n是基数为a的强（费马）可能素数 。 复合强基a （费马）可能素数被称为基（ a ）的强（费马）伪赝。 强Fermat pseudoprimes甚至比普通Fermat pseudoprimes更罕见，低于1000000，有78498个primes，245个base-2 Fermat pseudoprimes和只有46个base-2强Fermat pseudoprimes。 更重要的是，对于任何奇数复合物n ，最多有(n-9)/4碱基1 < a < n-1 ，其中n是强Fermat pseudoprime。
因此，如果n是奇数复合，则n在1和n-1之间随机选择的基数通过k强费马测试的概率（不包括边界）小于1/4^k 。
一个强大的费马测试采用O（log n）步，每一步涉及一个或两个数字的乘法与O（log n）位，因此复杂度为O（（log n）^ 3）与天真乘法[对于巨大的n ，更复杂的乘法算法是值得的]。
Miller-Rabin检验是随机选择的碱基的k倍强Fermat检验。 这是一种概率测试，但是对于足够小的界限，已知碱基的短组合，其给出确定性结果。
强Fermat测试是确定性APRCL测试的一部分。
建议在此类测试之前通过前几个小素数进行试验划分，因为划分相对便宜并且淘汰了大多数复合材料。
对于找到第n 个素数的问题，在测试素数的所有数字是可行的范围内，有已知的基数组合使多重强Fermat检验正确，因此可以提供更快的速度 - O（n *（log） n） 4 ） - 算法。
对于n < 2^32 ，碱基2,7和61足以validation质数。 使用它，大约六分钟就能找到第一亿个素数。
通过主要的除数，Eratosthenes的Sieve消除复合材料
不是按顺序调查数字并检查每个数字是否从头开始，也可以将整组相关数字视为一个整体，并一次性消除给定素数的倍数。 这被称为Eratosthenes的筛子：
找到不超过N的素数
- 列出从2到
N的所有数字 - 对于从2到
N每个k：如果k还没有被划掉，那么它是素数; 交叉掉所有的k倍数作为复合材料
素数是列表中没有划掉的数字。
该算法与试验划分根本不同，虽然两者都直接使用素数的可分性表征，与Fermat测试和使用素数的其他属性的类似测试相反。
在试验区中，每个数字n与所有不超过√n和n的最小素数的素数配对。 由于大多数复合材料具有非常小的素数除数，因此检测复合材料在这里平均很便宜。 但是测试质数是昂贵的，因为√n以下的素数相对较多。 虽然复合材料比复合材料多得多，但测试质数的成本非常高，以至于它完全控制了整体运行时间，并使试验分区成为一种相对较慢的算法。 对于小于N所有数字的试验除法采用O（N 1.5 /（log N）²）步。
在筛子中，每个复合物n与其所有主要除数配对，但仅与那些相比。 因此，素数是便宜的数字，它们只被看过一次，而复合材料更昂贵，它们被多次划掉。 人们可能会认为，由于筛子包含的“昂贵”数字比“廉价”数字更多，因此整体上算法很糟糕。 但是，复合数不具有许多不同的素数除数 - n的不同质数除数的数量由log n ，但通常它小得多，数字<= n的不同质数除数的平均值是log log n - 所以即使筛子中的“昂贵”数字平均也不比试验部门的“廉价”数字贵（或几乎不多）。
扫描到N ，对于每个素数p ，有Θ(N/p)倍数交叉，所以交叉总数的关闭是Θ(∑ (N/p)) = Θ(N * log (log N)) 。 与使用更快的素性测试的试验划分或顺序测试相比，这可以产生更快的算法，用于查找高达N的素数。
然而，筛子的缺点是它使用O(N)记忆。 （但是使用分段筛，可以减少到O(√N)而不会增加时间复杂度。）
为了找到第n 个素数，而不是素数高达N ，还存在一个问题，即事先不知道筛子应该到达多远。
后者可以使用素数定理求解。 PNT说
π(x) ~ x/log x (equivalently: lim π(x)*log x/x = 1),
其中π(x)是不超过x的素数的数量（此处和下面， log必须是自然对数，对于算法的复杂性，选择哪个基数用于对数并不重要）。 由此得出p(n) ~ n*log n ，其中p(n)是第n 个素数，并且从深度分析中已知有p(n)良好上界，特别是
n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6.
因此可以使用它作为筛分限制，它不会远远超过目标。
通过使用分段筛可以克服O(N)空间要求。 然后，可以记录√N以下的素数，用于O(√N / log N)存储器消耗，并使用增加长度的段（当筛子接近N时，O（√N））。
如上所述，算法有一些简单的改进：
- 开始只在
p²处穿过p倍数，而不是在2*p - 消除筛子中的偶数
- 从筛子中消除多个进一步的小质数
这些都不会降低算法的复杂性，但它们都会大幅减少常数因子（与试验除法相比，消除p的倍数会产生较小p较小加速，同时增加代码复杂度，而不是较小的p ）。
使用前两个改进产生
// Entry k in the array represents the number 2*k+3, so we have to do // a bit of arithmetic to get the indices right. public static int nthPrime(int n) { if (n < 2) return 2; if (n == 2) return 3; int limit, root, count = 1; limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3; root = (int)Math.sqrt(limit) + 1; limit = (limit-1)/2; root = root/2 - 1; boolean[] sieve = new boolean[limit]; for(int i = 0; i < root; ++i) { if (!sieve[i]) { ++count; for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) { sieve[j] = true; } } } int p; for(p = root; count < n; ++p) { if (!sieve[p]) { ++count; } } return 2*p+1; }
它在大约18秒内找到了数亿个素数，2038074743。 这个时间可以减少到大约15秒（这里是YMMV），通过存储打包的标志，每个标志一位，而不是boolean ，因为减少的内存使用量提供了更好的缓存局部性。
打包标志，消除3的倍数，并使用bit-twiddling更快的计数，
// Count number of set bits in an int public static int popCount(int n) { n -= (n >>> 1) & 0x55555555; n = ((n >>> 2) & 0x33333333) + (n & 0x33333333); n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); return (n * 0x01010101) >> 24; } // Speed up counting by counting the primes per // array slot and not individually. This yields // another factor of about 1.24 or so. public static int nthPrime(int n) { if (n < 2) return 2; if (n == 2) return 3; if (n == 3) return 5; int limit, root, count = 2; limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3; root = (int)Math.sqrt(limit); switch(limit%6) { case 0: limit = 2*(limit/6) - 1; break; case 5: limit = 2*(limit/6) + 1; break; default: limit = 2*(limit/6); } switch(root%6) { case 0: root = 2*(root/6) - 1; break; case 5: root = 2*(root/6) + 1; break; default: root = 2*(root/6); } int dim = (limit+31) >> 5; int[] sieve = new int[dim]; for(int i = 0; i < root; ++i) { if ((sieve[i >> 5] & (1 << (i&31))) == 0) { int start, s1, s2; if ((i & 1) == 1) { start = i*(3*i+8)+4; s1 = 4*i+5; s2 = 2*i+3; } else { start = i*(3*i+10)+7; s1 = 2*i+3; s2 = 4*i+7; } for(int j = start; j < limit; j += s2) { sieve[j >> 5] |= 1 << (j&31); j += s1; if (j >= limit) break; sieve[j >> 5] |= 1 << (j&31); } } } int i; for(i = 0; count < n; ++i) { count += popCount(~sieve[i]); } --i; int mask = ~sieve[i]; int p; for(p = 31; count >= n; --p) { count -= (mask >> p) & 1; } return 3*(p+(i<<5))+7+(p&1); }
在大约9秒钟内找到了数亿个素数，这并不是无法忍受的长。
还有其他类型的素子筛，特别感兴趣的是阿特金的筛子，它利用了某些同余类（理性）素数是ℚ的一些二次扩展的代数整数环中的复合物这一事实。 这里不是扩展数学理论的地方，只要说Atkin的Sieve比Eratosthenes的Sieve具有更低的算法复杂度，因此对于大的限制是优选的（对于小的限制，没有过度优化的Atkin筛具有更高的限制开销因此可能比同等优化的Eratosthenes筛更慢。 DJ Bernstein的primegen库（用C语言编写）针对低于2 32的数字进行了优化，并在大约1.1秒内找到了数亿个素数（此处）。
快捷的方式
如果我们只想找到第n 个素数，那么找到所有较小的素数也没有内在价值。 如果我们可以跳过大部分内容，我们可以节省大量时间和工作。 给定a a(n)与第n 个素数p(n)的良好近似，如果我们有一种快速的方法来计算素数π(a(n))不超过a(n) ，我们就可以筛选一个小的范围高于或低于a(n)以识别a(n)和p(n)之间的少数缺失或过量的素数。
我们已经看到了一个很容易计算的上面p(n)相当好的近似值，我们可以采用
a(n) = n*(log n + log (log n))
例如。
计算π(x)一个好方法是Meissel-Lehmer方法 ，它在大约O(x^0.7)时间内计算π(x) （确切的复杂性取决于实现，Lagarias，Miller，Odlyzko，Deléglise的改进）和Rivat让一个在π(x) x 2/3 /log²x）时间内计算π(x) ）。
从简单近似a(n) ，我们计算e(n) = π(a(n)) - n 。 根据素数定理， a(n)附近的素数密度约为1/log a(n) ，因此我们期望p(n)接近b(n) = a(n) - log a(n)*e(n)我们将筛选比log a(n)*e(n)略大的范围。 为了更有信心p(n)处于筛分范围内，可以将范围增加2倍，比如几乎肯定足够大。 如果范围看起来太大，可以用更好的近似值b(n)代替b(n)迭代，计算π(b(n))和f(n) = π((b(n)) - n通常， |f(n)|将远小于|e(n)| 。如果f(n)大约是-e(n) ，则c(n) = (a(n) + b(n)) / 2将是p(n)的更好近似。只有在非常不可能的情况下， f(n)非常接近e(n) （并且非常接近0），找到一个足够好的近似p(n)最终筛分阶段可以在与计算π(a(n))相当的时间内完成成为问题。
通常，在初始近似的一次或两次改进之后，筛分的范围足够小以使筛分阶段具有O（n ^ 0.75）或更好的复杂性。
这种方法在大约40毫秒内找到第一百万个素数，在10秒内找到10 12个素数，29996224275833。
tl; dr：找到第n 个素数可以有效地完成，但是你想要的效率越高，所涉及的数学就越多。
我有大量所讨论的算法的Java代码，以防有人想要使用它们。
¹除了对过度兴趣的灵魂的评论：现代数学中使用的素数的定义是不同的，适用于更一般的情况。 如果我们调整学校定义以包括负数 - 所以如果一个数字既不是1也不是-1并且只能被1，-1本身和它的负数整除 - 它定义（对于整数）现在称为不可约元素的数字是素数然而，对于整数，素数和不可约元素的定义是一致的。
int counter = 0; for(int i = 1; ; i++) { if(isPrime(i) counter++; if(counter == userInput) { print(i); break; } }
编辑：你的主要function可以使用一些工作。 这是我写的一个：
private static boolean isPrime(long n) { if(n < 2) return false; for (long i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; }
注意 - 在查看因子时，您只需要达到sqrt（n），因此i * i <= n
你试图在main方法中做太多。 您需要将其分解为更易于管理的部分。 编写方法boolean isPrime(int n) ，如果数字为素数则返回true，否则返回false。 然后修改main方法以使用isPrime。
java.math.BigInteger有一个nextProbablePrime（）方法。 虽然我猜这是用于加密的，你可以用它来工作。
BigInteger prime = BigInteger.valueOf(0); for (int i = 0; i < n; i++) { prime = prime.nextProbablePrime(); } System.out.println(prime.intValue());
我刚刚在你自己的思考过程中添加了缺失的行。
static int nthPrimeFinder（int n）{
int counter = 1; // For 1 and 2. assuming n is not 1 or 2. int i = 2; int x = 2; int tempLength = n; while (counter <= n) { for (; i <= tempLength; i++) { for (x = 2; x < i; x++) { if (i % x == 0) { break; } } if (x == i && counter < n) { //System.out.printf("\n%d is prime", x); counter++; if (counter == n) { System.out.printf("\n%d is prime", x); return counter; } } } tempLength = tempLength+n; } return 0; }
public class prime{ public static void main(String ar[]) { int count; int no=0; for(int i=0;i<1000;i++){ count=0; for(int j=1;j<=i;j++){ if(i%j==0){ count++; } } if(count==2){ no++; if(no==Integer.parseInt(ar[0])){ System.out.println(no+"\t"+i+"\t") ; } } } } }
我可以看到你收到了许多正确的答案和非常详细的答案。 我相信你没有为非常大的素数测试它。 而您唯一关心的是避免通过您的程序打印中间素数。
一个微小的改变你的程序将成功。
保持逻辑相同，只需在循环外拉出print语句。 在n个素数后打破外部循环。
import java.util.Scanner; /** * Calculates the nth prime number * @author {Zyst} */ public class Prime { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n, i = 2, x = 2; System.out.printf("This program calculates the nth Prime number\n"); System.out.printf("Please enter the nth prime number you want to find:"); n = input.nextInt(); for(i = 2, x = 2; n > 0; i++) { for(x = 2; x < i; x++) { if(i % x == 0) { break; } } if(x == i) { n--; } } System.out.printf("\n%d is prime", x); } }
使用Java 8 parallelStream会更快。 下面是我查找第N个素数的代码
public static Integer findNthPrimeNumber(Integer nthNumber) { List primeList = new ArrayList<>(); primeList.addAll(Arrays.asList(2, 3)); Integer initializer = 4; while (primeList.size() < nthNumber) { if (isPrime(initializer, primeList)) { primeList.add(initializer); } initializer++; } return primeList.get(primeList.size() - 1); } public static Boolean isPrime(Integer input, List primeList) { return !(primeList.parallelStream().anyMatch(i -> input % i == 0)); } @Test public void findNthPrimeTest() { Problem7 inputObj = new Problem7(); Integer methodOutput = inputObj.findNthPrimeNumber(100); Assert.assertEquals((Integer) 541, methodOutput); Assert.assertEquals((Integer) 104743, inputObj.findNthPrimeNumber(10001)); }
虽然有许多正确和详细的解释。 但这是我的C实现：
#include #include main() { int pk,qd,am,no,c=0; printf("\n Enter the Number U want to Find"); scanf("%d",&no); for(pk=2;pk<=1000;pk++) { am=0; for(qd=2;qd<=pk/2;qd++) { if(pk%qd==0) { am=1; break; }} if(am==0) c++; if(c==no) { printf("%d",pk); break; }} getch(); return 0; }