最有效的code为第10000素数？ [英] Most efficient code for the first 10000 prime numbers?

问题描述

我要打印第10000素数。 谁能给我最有效的code这个？ 说明：

1. 在这不要紧，如果你的code是低效对于n＆GT; 10000
2. 的code的大小并不重要。
3. 您不能只是很难code以任何方式的值。

解决方案

阿特金的 筛子可能是你要找的内容，它的上限运行时间为O（N /日志日志N）。

如果你只能运行数比为6的倍数1以上1以下时，也可能是得更快，因为所有的质数以上3的1个远离6的某个倍数。 资源为我的发言

I want to print the first 10000 prime numbers. Can anyone give me the most efficient code for this? Clarifications:

1. It does not matter if your code is inefficient for n >10000.
2. The size of the code does not matter.
3. You cannot just hard code the values in any manner.

解决方案

The Sieve of Atkin is probably what you're looking for, its upper bound running time is O(N/log log N).

If you only run the numbers 1 more and 1 less than the multiples of 6, it could be even faster, as all prime numbers above 3 are 1 away from some multiple of six. Resource for my statement

这篇关于最有效的code为第10000素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！