我想打印前 10000 个素数。谁能给我最有效的代码？说明：
- 如果您的代码在 n > 10000 时效率低下，则无关紧要。
- 代码的大小无关紧要。
- 您不能以任何方式对值进行硬编码。
Niyaz
问问题
69235 次
30 回答
39
筛子或 Eratosthenes 可能是查找素数列表的最直观的方法。基本上你：
- 写下从 2 到您想要的任何限制的数字列表，比如说 1000。
- 取第一个没有被划掉的数字（对于第一次迭代，这是 2）并从列表中划掉该数字的所有倍数。
- 重复步骤 2，直到到达列表末尾。所有没有划掉的数字都是素数。
显然，可以进行很多优化以使该算法更快地工作，但这是基本思想。
Atkin 的筛子使用了类似的方法，但遗憾的是我对此了解的不够多，无法向您解释。但我确实知道，我链接的算法需要 8 秒才能计算出古代 Pentium II-350 上 1000000000 以内的所有素数
阿特金筛源代码：http ://cr.yp.to/primegen.html
于 2008-08-05T23:49:43.963 回答
20
这并不严格违反硬编码限制，但非常接近。为什么不以编程方式下载此列表并将其打印出来呢？
于 2008-08-31T22:20:44.647 回答
13
GateKillerbreak，if在foreach循环中添加一个怎么样？这会大大加快速度，因为如果像 6 可以被 2 整除，您就不需要检查 3 和 5。（如果我有足够的声誉，我会投票支持您的解决方案:-) ... ）
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
于 2008-08-27T20:26:27.947 回答
13
在 Haskell 中，我们几乎可以逐字逐句写下埃拉托色尼筛的数学定义，“素数是大于 1 的自然数，没有任何合数，通过枚举每个素数的倍数来找到合数”：
import Data.List.Ordered (minus, union)
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000几乎是瞬时的。
参考：
上面的代码很容易调整为仅处理赔率，primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). 通过折叠成树状结构可以大大提高时间复杂度（大约比最佳值高一个对数因子），并且通过多级素数生产可以显着提高空间复杂度，在
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
（在 Haskell 中，括号用于分组，函数调用仅通过并列表示，(:)是列表的cons运算符，并且(.)是函数组合运算符：）(f . g) x = (\y -> f (g y)) x = f (g x)。
于 2012-04-24T16:30:15.850 回答
11
@Matt: log(log(10000)) 是~2
从维基百科文章（你引用的）阿特金筛子：
O(N/log log N)该筛子使用仅具有 N 1/2+o(1)位内存的操作来计算最多 N 个素数。O(N)这比使用操作和 O(N 1/2 (log log N)/log N) 位内存的 Eratosthenes 的筛子要好一些（AOL Atkin，DJ Bernstein，2004）。这些渐近计算复杂性包括简单的优化，例如车轮分解，以及将计算拆分为更小的块。
O(N)考虑到（对于 Eratosthenes）和（对于 Atkin）的渐近计算复杂性，O(N/log(log(N)))我们不能说（对于 small N=10_000）如果实施哪种算法会更快。
Achim Flammenkamp 在The Sieve of Eratosthenes中写道：
被引用：
@num1
对于大于 10^9 的区间，当然对于大于 10^10 的区间，埃拉托色尼筛法的性能要优于使用不可约二元二次形式的阿特金斯和伯恩斯坦筛法。有关背景信息，请参阅他们的论文以及 W. Galway 博士的第 5 段。论文。
因此，对于10_000Eratosthenes 的 Sieve 可以比 Atkin 的 Sieve 更快。
要回答 OP，代码是prime_sieve.c（由 引用num1）
于 2008-10-06T20:03:30.423 回答
10
使用 GMP，可以编写以下内容：
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
在我的 2.33GHz Macbook Pro 上，它执行如下：
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
在同一台笔记本电脑上计算 1,000,000 个素数：
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP 针对这类事情进行了高度优化。除非您真的想通过编写自己的算法来理解算法，否则建议您在 C 下使用 libGMP。
于 2008-08-29T07:06:43.937 回答
7
根本没有效率，但您可以使用正则表达式来测试素数。
/^1?$|^(11+?)\1+$/
这将测试，对于由k个“<code>1”组成的字符串，k是否不是素数（即该字符串是由一个“<code>1”还是由任意数量的“<code>1”组成，可以表示为n元积）。
于 2008-08-03T18:52:17.093 回答
5
我已经修改了CodeProject上的代码来创建以下内容：
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
在我的 ASP.NET 服务器上进行测试需要大约 1 分钟的时间。
于 2008-08-05T19:55:17.557 回答
4
Eratosthenes 的筛子是要走的路，因为它简单且速度快。我在 C 中的实现
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
查找素数的 CPU 时间（在 Pentium Dual Core E2140 1.6 GHz 上，使用单核）
~ 4s for lim = 100,000,000
于 2008-08-20T23:45:54.110 回答
3
这是我几天前在 PowerShell 中编写的 Eratosthenes 筛。它有一个参数，用于标识应返回的素数数量。
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
于 2009-09-07T18:52:12.030 回答
2
改编自GateKiller并继续使用，这是我使用的最终版本。
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
基本相同，但我添加了“Sqrt 中断”建议并更改了一些变量以使其更适合我。（我正在研究欧拉，需要第 10001 个素数）
于 2009-02-16T05:17:44.037 回答
2
筛子似乎是错误的答案。筛子为您提供最多为N的素数，而不是前 N 个素数。运行@Imran 或@Andrew Szeto，你得到的素数最多为 N。
如果您继续尝试筛子以获得越来越大的数字，直到您达到一定大小的结果集，并使用一些已经获得的数字缓存，筛子可能仍然可用，但我相信它仍然不会比像@Pat's 这样的解决方案快.
于 2009-06-19T18:12:35.903 回答
2
在 Python 中
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
于 2010-02-22T07:45:46.507 回答
2
BenGoldberg 提到的双端队列筛算法值得仔细研究，不仅因为它非常优雅，还因为它在实践中偶尔有用（不像 Atkin 的筛子，这是一个纯粹的学术练习）。
双端队列筛算法背后的基本思想是使用一个小的滑动筛，它的大小仅足以包含每个当前“活动”素数因子的至少一个单独的倍数 - 即平方不超过最小数的素数目前以移动筛为代表。与 SoE 的另一个区别是双端队列筛将实际因子存储到复合的槽中，而不是布尔值。
该算法根据需要扩展筛子窗口的大小，从而在很宽的范围内实现相当均匀的性能，直到筛子开始明显超过 CPU 的 L1 高速缓存的容量。最后一个完全拟合的素数是 25,237,523（第 1,579,791 个素数），这为算法的合理操作范围提供了一个粗略的数字。
该算法相当简单和健壮，甚至比未分段的埃拉托色尼筛法在更广泛的范围内具有性能。后者要快得多，只要它的筛子完全适合缓存，即对于具有字节大小布尔值的仅赔率筛子，最多 2^16。然后它的性能越来越下降，尽管它总是比双端队列快得多，尽管有障碍（至少在 C/C++、Pascal 或 Java/C# 等编译语言中）。
这是 C# 中 deque sieve 算法的渲染，因为我发现这种语言 - 尽管有许多缺陷 - 对于原型算法和实验来说比极其繁琐和迂腐的 C++ 更实用。（旁注：我正在使用免费的LINQPad，它可以让我直接投入其中，而无需设置项目、makefile、目录或诸如此类的所有混乱，并且它为我提供了与 python 提示相同程度的交互性）。
C# 没有显式的双端队列类型，但纯List<int>文本足以很好地演示算法。
注意：这个版本没有对素数使用双端队列，因为从 n 个素数中弹出 sqrt(n) 根本没有意义。去掉 100 个素数并留下 9900 有什么好处？至少通过这种方式，所有素数都被收集在一个整洁的向量中，为进一步处理做好准备。
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
下面是两个辅助函数：
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
理解该算法的最简单方法可能是将其想象为一个特殊的分段埃拉托色尼筛，分段大小为 1，伴随着一个溢出区域，当素数射过分段末端时，它们会在该溢出区域停止。除了段的单个单元格（aka sieve[0]）在我们到达它时已经被筛选，因为它在溢出区域的一部分时被碾过。
由 表示的数字sieve[0]保存在 中sieve_base，尽管sieve_frontorwindow_base也是一个好名字，可以与 Ben 的代码或分段/窗口筛的实现相比较。
如果sieve[0]包含一个非零值，则该值是 的一个因子sieve_base，因此可以被识别为复合的。由于单元 0 是该因子的倍数，因此很容易计算其下一跳，即 0 加上该因子。如果该单元格已经被另一个因子占据，那么我们只需再次添加该因子，依此类推，直到我们找到当前没有其他因子停放的因子的倍数（如果需要，扩展筛子）。这也意味着不需要像在正常的分段筛中那样存储从一个段到下一个段的各种素数的当前工作偏移量。每当我们在 中找到一个因子时sieve[0]，它的当前工作偏移量为 0。
当前的素数通过以下方式发挥作用。一个素数只有在它自己出现在流中后才能成为当前的（即当它被检测为素数时，因为没有用因子标记），并且它将保持当前状态，直到sieve[0]到达它的平方的确切时刻。由于较小的素数的活动，这个素数的所有较低倍数都必须被剔除，就像在正常的 SoE 中一样。但是没有一个较小的素数可以从正方形中删除，因为正方形的唯一因素是素数本身，并且此时它还没有流通。这解释了算法在这种情况下采取的行动sieve_base == current_prime_squared（顺便说一句，这意味着sieve[0] == 0）。
现在这种情况sieve[0] == 0 && sieve_base < current_prime_squared很容易解释：这意味着它sieve_base不能是任何小于当前素数的素数的倍数，否则它会被标记为合数。I 也不能是当前素数的更高倍数，因为它的值小于当前素数的平方。因此它必须是一个新的素数。
该算法显然受到埃拉托色尼筛法的启发，但同样明显的是，它非常不同。埃拉托色尼筛法的卓越速度源于其基本操作的简单性：一个单一的索引添加和一个操作的每个步骤的存储是它在很长一段时间内所做的一切。
这是一个简单的、未分段的 Eratosthenes 筛，我通常使用它来筛选 ushort 范围内的因子素数，即高达 2^16。对于这篇文章，我已通过替换将其修改为超过 2^ int16ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
在筛选前 10000 个素数时，将超过 32 KiByte 的典型 L1 缓存，但该函数仍然非常快（即使在 C# 中也只有几分之一毫秒）。
如果将此代码与 deque sieve 进行比较，那么很容易看出 deque sieve 的操作要复杂得多，并且它无法有效地摊销其开销，因为它总是连续进行最短可能的交叉操作（在跳过所有已经被划掉的倍数之后，正好是一个划线）。
注意：C# 代码使用int而不是，uint因为较新的编译器习惯于为 生成不合标准的代码uint，可能是为了将人们推向有符号整数......在上面我使用的代码的 C++ 版本中unsigned，自然；基准必须在 C++ 中，因为我希望它基于所谓的足够的双端队列类型（std::deque<unsigned>；使用 没有性能提升unsigned short）。以下是我的 Haswell 笔记本电脑 (VC++ 2015/x64) 的编号：
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
注意：C# 时间几乎是 C++ 时间的两倍，这对 C# 来说非常好，并且表明List<int>即使被滥用为双端队列也不会懈怠。
简单的筛选代码仍然会将双端队列从水中吹走，即使它已经在其正常工作范围之外运行（L1 缓存大小超过 50%，伴随着缓存抖动）。这里的主要部分是筛选出的素数的读取，这不受缓存问题的影响很大。在任何情况下，该函数都是为筛选因素的因素而设计的，即 3 级筛选层次结构中的第 0 级，通常它只需要返回几百个因素或少量的数千个因素。因此它的简单性。
通过使用分段筛并优化用于提取已筛出的素数的代码（步进 mod 3 并展开两次，或 mod 15 并展开一次），性能可以提高一个数量级以上，并且可以挤出更多的性能代码通过使用带有所有装饰的 mod 16 或 mod 30 轮子（即所有残留物的完全展开）。类似的事情在我对代码审查中查找素数定位素数的回答中进行了解释，其中讨论了类似的问题。但是很难看出为一次性任务改进亚毫秒时间的意义......
为了让事情更深入一点，这里是筛选多达 100,000,000 个的 C++ 时间：
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
相比之下，C# 中带有一些花里胡哨的分段筛子在 95 毫秒内完成了相同的工作（没有可用的 C++ 计时，因为我目前只在 C# 中进行代码挑战）。
在像 Python 这样的解释型语言中，情况可能看起来完全不同，其中每个操作都有很高的成本，并且解释器开销使由于预测与错误预测的分支或子周期操作（移位、加法）与多周期操作（乘法）造成的所有差异相形见绌，甚至是除法）。这势必会削弱埃拉托色尼筛法的简单性优势，这可能会使双端队列解决方案更具吸引力。
此外，该主题中其他受访者报告的许多时间可能都以输出时间为主。那是一场完全不同的战争，我的主要武器是这样一个简单的类：
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
写入 10000 个（排序的）数字需要不到 1 毫秒的时间。它是一个静态类，因为它旨在将文本包含在编码挑战提交中，以最少的麻烦和零开销。
一般来说，我发现如果对整个批次进行集中工作会更快，这意味着筛选某个范围，然后将所有素数提取到一个向量/数组中，然后爆破整个数组，然后筛选下一个范围等等，而不是将所有东西混合在一起。具有专注于特定任务的单独功能还可以更容易地混合和匹配，它可以重用，并且可以简化开发/测试。
于 2016-04-19T17:07:28.123 回答
1
这是我的 VB 2008 代码，它在我的工作笔记本电脑上在 1 分 27 秒内找到所有质数 <10,000,000。它会跳过偶数，只查找小于测试数 sqrt 的素数。它仅用于查找从 0 到标记值的素数。
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
于 2011-03-11T02:25:23.013 回答
1
以下 Mathcad 代码在 3 分钟内计算出前一百万个素数。
请记住，这将对所有数字使用浮点双精度，并且基本上可以解释。我希望语法清楚。
于 2014-03-02T01:15:02.170 回答
1
这是一个使用 SoE 形式的 C++ 解决方案：
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
请注意，这个版本的 Sieve 可以无限地计算素数。
另请注意，STL通过下标执行、、和随机访问deque需要时间。O(1)push_backpop_front
该resize操作需要O(n)时间，其中n是要添加的元素的数量。由于我们使用此函数的方式，我们可以将其视为一个小常数。
while循环体inmy_insert是执行O(log log n)次数，其中n等于变量maybe_prime。这是因为对于 的每个素因子， 的条件表达式while将计算为真一次maybe_prime。请参阅Wikipedia 上的“除数函数”。
乘以次数my_insert被称为，表明O(n log log n)列出素数应该花费时间n......这就是埃拉托色尼筛应该具有的时间复杂度，这并不奇怪。
然而，虽然这段代码很有效，但它并不是最有效的......我强烈建议使用专门的库来生成素数，例如primesieve。任何真正高效、优化良好的解决方案都需要比任何人都想输入到 Stackoverflow 中的更多代码。
于 2016-04-16T18:33:01.887 回答
1
使用埃拉托色尼筛法，与“已知范围”的素数算法相比，计算速度要快得多。
通过使用它的 wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) 中的伪代码，我可以在 C# 上找到解决方案。
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) 需要 2 秒和 330 毫秒。
注意：值可能因硬件规格而异。
于 2016-05-12T03:40:03.553 回答
1
这是我的代码，它在我的笔记本电脑上在 0.049655 秒内找到前 10,000 个质数，在 6 秒内找到前 1,000,000 个质数，在 15 秒内找到前 2,000,000 个
一点解释。此方法使用 2 种技术来查找素数
- 首先，任何非素数都是素数的倍数的组合，因此此代码通过将测试数除以较小的素数而不是任何数字来进行测试，这对于 4 位数字减少了至少 10 倍的计算，甚至更多更大的数字
- 其次，除了除以素数之外，它只除以小于或等于被测试数的根的素数，这进一步减少了计算，这是因为任何大于该数的根的数都会有一个对应数必须小于数字的根，但是由于我们已经测试了所有小于根的数字，因此我们不需要为大于所测试数字的根的数字而烦恼。
前 10,000 个素数的示例输出
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
这是 C 语言的代码，输入 1 然后输入 10,000 以打印出前 10,000 个素数。
编辑：我忘记了这个包含数学库，如果你在 Windows 或 Visual Studio 上应该没问题，但在 Linux 上你必须使用 -lm 参数编译代码，否则代码可能不起作用
示例：gcc -Wall -o "%e " "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
于 2017-05-06T11:48:38.673 回答
0
我用python写了这个，因为我刚开始学习它，它工作得很好。此代码生成的第 10,000 个素数与http://primes.utm.edu/lists/small/10000.txt中提到的相同。要检查是否n是素数，请除以n从2到的数字sqrt(n)。如果这个数字范围中的任何一个完全划分n，那么它就不是素数。
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
于 2010-12-27T17:37:23.507 回答
0
我花了一些时间编写一个计算大量素数的程序，这是我用来计算包含前 1.000.000.000 个素数的文本文件的代码。它是德语的，但有趣的部分是方法calcPrimes()。素数存储在名为 Primzahlen 的数组中。我推荐使用 64 位 CPU，因为计算是使用 64 位整数。
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
于 2012-04-23T19:46:21.880 回答
0
我一直致力于寻找素数大约一年。这是我发现最快的：
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 纳秒从 2 开始到达 2147483629。
于 2016-08-14T00:20:37.247 回答
0
这是我制作的代码：
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
于 2018-01-20T15:50:48.837 回答
0
在 Javascript 中使用 Array.prototype.find() 方法。2214.486 毫秒
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
于 2018-06-09T21:49:48.420 回答
0
我可以给你一些提示，你必须执行它。
- 对于每个数字，得到该数字的一半。例如，对于检查 21，仅通过将其从范围 2-10 中除来获得余数。
- 如果是奇数，只除以奇数，反之亦然。如 21，只除以 3、5、7、9。
到目前为止我最有效的方法。
于 2018-07-29T19:25:08.200 回答
0
由于您只想要前 10000 个素数，而不是编写复杂的算法，我将建议以下
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
现在呼叫是您需要的首要任务
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
于 2018-11-16T05:34:35.510 回答
0
这是一个老问题，但这里每个人都缺少一些东西......
对于这么小的素数，试除法并没有那么慢……只有 25 个低于 100 的素数。要测试的素数这么少，而且这么小的素数，我们可以拿出一个巧妙的把戏！
如果 a 与 b 互质，则 gcd ab = 1。互质。有趣的词。意味着它不共享任何主要因素。因此，我们可以通过一次 GCD 调用来测试多个素数的可分性。多少？嗯，前 15 个素数的乘积小于 2^64。并且接下来10的乘积也小于2^64。这就是我们需要的全部 25 个。但是这值得吗？
让我们来看看：
check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes
a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes
Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)
那里提高了 6 倍。
（length是强制计算列表。默认情况下，Haskell 一次打印 1 个 Unicode 字符，因此实际打印列表将支配时间或支配实际使用的代码量。）
当然，这是在 GHCi 中运行的——一个运行解释代码的 repl——在旧笔记本电脑上，它不会将这些数字中的任何一个解释为int64s 甚至BigInts，即使你要求它也不会（好吧，你可以强制它，但它很丑陋，并没有真正的帮助）。它将那里的每个数字解释为可以通过字典查找专门针对某些特定类型的通用整数类事物，并且它正在遍历链表（由于未编译，此处未融合）3次。有趣的是，手动融合两个过滤器实际上会减慢 REPL 中的速度。
让我们编译它：
...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total time 0.000s ( 0.004s elapsed)
使用 RTS 报告，因为 Windows。一些行被修剪是因为它们不相关——它们是其他 GC 数据，或者只是部分执行的测量值，加起来等于 0.004 秒（或更少）。它也不是不断折叠，因为 Haskell 实际上并没有做太多。如果我们不断地折叠自己（main = print 10000），我们会得到显着降低的分配：
...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total time 0.000s ( 0.001s elapsed)
从字面上看，足以加载运行时，然后发现除了打印一个数字并退出之外别无他法。让我们添加车轮分解：
wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel
Total time 0.000s ( 0.003s elapsed)
相对于我们的参考减少了大约 1/3 main = print 10000，但肯定还有更多优化的空间。例如，它实际上停止在那里执行 GC，而通过调整不应该有任何堆使用。出于某种原因，在此处进行分析编译实际上将运行时间缩短到 2 毫秒：
Tue Nov 12 21:13 2019 Time and Allocation Profiling Report (Final)
Primes.exe +RTS -p -RTS
total time = 0.00 secs (2 ticks @ 1000 us, 1 processor)
total alloc = 967,120 bytes (excludes profiling overheads)
我现在将保持原样，我很确定随机抖动开始占主导地位。
于 2019-11-13T02:49:48.077 回答
0
def compute_primes(bound):
"""
Return a list of the prime numbers in range(2, bound)
Implement the Sieve of Eratosthenes
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
"""
primeNumber = [True for i in range(bound + 1)]
start_prime_number = 2
primes = []
while start_prime_number * start_prime_number <=bound:
# If primeNumber[start_prime_number] is not changed, then it is a prime
if primeNumber[start_prime_number]:
# Update all multiples of start_prime_number
for i in range(start_prime_number * start_prime_number, bound + 1, start_prime_number):
primeNumber[i] = False
start_prime_number += 1
# Print all prime numbers
for start_prime_number in range(2, bound + 1):
if primeNumber[start_prime_number]:
primes.append(start_prime_number)
return primes
打印(len(compute_primes(200)))
打印（len（compute_primes（2000）））
于 2020-05-16T03:52:19.613 回答
-1
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
于 2012-05-08T04:15:08.367 回答