问题标签 [sieve]

我的老师给了我这个：

n<=10^6;

n 个整数数组：ai..an(ai<=10^9);

找到所有素数。

他说了一些关于 eratosthenes 筛子的事情，我读过它，还有轮分解，但我仍然不知道如何让程序（fpc）在 1 秒内运行。？？据我所知这是不可能的，但仍然想知道你的意见。并且通过车轮分解，一个 2*3 的圆圈会将 25 视为素数，我想问是否有办法找出被错误视为素数的车轮的第一个数字。示例：2*3*5 圆，如何找到第一个被视为质数的合数？请帮忙..对不起英语不好。

我正在练习编写针对空间或时间复杂度进行优化的算法。使用素数筛，您至少必须存储找到的所有素数的列表。似乎与找到的素数成比例的数据是这种算法可能使用的最少空间。

• 这个理由有效吗？
• 如何评估该算法的空间复杂度？

来自关于阿特金筛子的维基百科- 我不确定当素数数量超过此值时，筛子如何使用 O(n^1/2) 空间。这就是为什么看起来至少空间必须与素数的数量成比例的原因。我是否将可数数字与空间复杂度混淆了？

在这篇关于 Atkin 筛子的论文中，他们的算法打印“最多为 N 的素数......这里的“内存”不包括打印机使用的纸张。” 这似乎是对空间的不公平计算。

• 我希望澄清这应该如何/实际上是客观地衡量的。

我偶然发现了以下问题：我有一个类可以获取和打印 1 到 N 之间的所有素数。N 是您必须自己插入的参数。当我为 N 插入 10000 时，代码工作并打印出从 2 到最接近 N 的所有素数。

当我插入 40000 时，代码仍然有效。当我插入 50000（或更高）时，代码会给出 ArrayOutOfBoundsException。为什么？

这是我使用的代码：

并使用

点“priemgetallen.remove(j*i)”是我收到错误的地方。

如果有人能告诉我为什么这不适用于所有大于大约的 N，我将非常感激。40000。

提前致谢！

标准的 Eratosthenes 筛子可多次剔除大多数复合材料；事实上，唯一不会被多次标记的是那些恰好是两个素数的乘积。自然，随着筛子变大，透支也会增加。

对于奇数筛（即没有偶数筛），透支达到 100%，n = 3,509,227，有 1,503,868 个复合物和 1,503,868 个已划掉的数字。对于 n = 2^32，透支上升到 134.25%（透支 2,610,022,328 与弹出计数 1,944,203,427 = (2^32 / 2) - 203,280,221）。

Sundaram的筛子——在maths.org上有另一种解释——可能会更聪明一点，如果——且仅当——智能计算循环限制。然而，这就是我所看到的消息来源似乎掩盖为“优化”的东西，而且似乎未优化的 Sundaram 每次都会被只有赔率的 Eratosthenes 击败。

有趣的是，两者都创建了完全相同的最终位图，即位 k 对应于数字 (2 * k + 1) 的位图。所以两种算法最终都必须设置完全相同的位，它们只是有不同的处理方式。

是否有人亲身体验过具有竞争力的、经过调校的 Sundaram？它可以击败古希腊吗？

我已经精简了我的小因子筛子的代码（2^32，一个只有赔率的希腊语），并将段大小调整为 256 KB，这在具有 256 KB L2 的旧 Nehalem 上与在较新的 CPU 上一样最佳（甚至尽管后者对更大的细分市场更加宽容）。但是现在我撞到了一堵砖墙，血筛仍然需要 8.5 秒来初始化。从硬盘加载筛子不是一个非常有吸引力的选择，并且多线程很难以可移植的方式进行（因为像 boost 这样的库往往会使活动扳手进入可移植性）......

Sundaram 能否将启动时间缩短几秒钟？

PS：这样的透支不是问题，会被二级缓存吸收。关键是标准的埃拉托色尼似乎比必要的工作量增加了一倍以上，这表明可能有可能做更少的工作，更快。

小于 10,000,000 的素数数量为 664,579，但我的代码仅生成 664,214。数字来源是https://primes.utm.edu/howmany.html

小质数 - 最多约 1,000,000,000,000 - 很容易从各种来源获得。Prime Pages (utm.edu)有前 5000 万个素数的列表，primos.mat.br上升到 10^12，像primesieve.org上提供的程序甚至更高。

然而，当涉及到接近 2^64 的数字时，只有 Primes.utm.edu 页面上提到的十个素数小于 2的幂，似乎就是这样。

素数测试发现那里拒绝处理不适合双倍的数字，其他地方 - 其他地方 - 未能拒绝并且只是打印垃圾。primesieve.org 程序拒绝使用低于 2^64 至少 400 亿的数字，这并不能完全激发人们对其编码质量的信心。到处都是相同的结果：nada、zilch、niente。

筛子的齿轮和齿轮开始在 2^62 标记附近吱吱作响，接近 2^64 时几乎没有一个齿轮不发出响亮的吱吱声，威胁要破裂。因此，由于缺乏可靠的参考数据，在验证最困难的地方，测试实现的需求最大。primesieve.org 程序似乎是唯一一个至少可以工作到 2^63 左右的程序，但由于上述问题，我不太相信它。

那么如何才能验证接近 2^64 的筛子的正确操作呢？是否有可靠的列表包含一百万（或一千万或一亿）质数，刚好低于和高于 2 的幂，如 2^64、2^63 等等？或者是否有可靠的（值得信赖的、经过验证的、大量使用的）程序产生这样的序列或可以验证素数或素数列表？

一旦筛子得到验证，它就可以用来生成方便的列表，其中包含有大量有趣范围的总和/校验和，但如果没有这样的列表，情况似乎很困难......

PS：我将primesieve.org turbo siever的上限确定为0xFFFFFFF600000009 UINT64_MAX - 10 * UINT32_MAX。这意味着到目前为止，只有 10 * UINT32_MAX 最高质数根本没有任何参考数据......

我有一些表使用 jQuery 插件'tablesorter'来轻松排序。最近，我发现它包含一个斑马条纹小部件。我启用了它，它运行良好。

我还决定添加“Sieve”插件，以替代现有的自制表格搜索功能，这就是我的问题所在 - 在搜索期间或之后没有重做条带化，导致表格不均匀且不匹配。

到目前为止，我还没有找到一种方法让它手动刷新，而且我不确定如果有的话我会把它放在哪里 - 在 sieve .js 文件中？有没有办法让这两个插件相互配合？

我在学校有这个作业；我们将在 java 中编写一个简单的程序/方法/算法，让我们接受两个数字输入并输出两个输入之间范围内的所有数字的计数，这些输入可以被 2 或 3 或 5 整除。

分配相当简单，因为您可以遍历范围内的所有数字并在满足所有条件时递增计数器。

但是我们也得到了 10 个测试输入和一个评估我们算法效率的计时器。前八个失败，因为八个值 < 10 ^ 6。但是最后两个测试输入值 < 10^18 并且我的算法失败了。

于是我开始思考素数计数函数的方向并筛出埃拉托色尼，但我的头开始疼。关于更快但仍然足够简单的算法的任何想法？

这是我尝试使用的代码：这应该生成最多 100 的所有素数

我是 Haskell 编程的新手，无法理解以下列表理解如何扩展。

有人可以纠正我sieve扩展的工作原理：

• 当我们在 中进行模式匹配时sieve，p将关联到2和xs from [3..]。
• 接下来，在列表理解x<-3中，但是我们如何3在没有短路的情况下调用 sieve。

我不明白的另一件事是递归如何在这里工作。

我认为如果可以一次将上述一步扩展为前几个数字，比如直到5。