阿特金分段筛可能吗?

2023-11-23

我知道可以实现埃拉托斯特尼筛法,以便它连续找到素数而没有上限(分段筛)。

我的问题是,阿特金/伯恩斯坦筛法可以用同样的方式实现吗?

相关问题:C#:如何使阿特金筛增量

然而相关问题只有1个答案,即“对于所有筛子都是不可能的”,这显然是不正确的。


Atkin/Bernstein 在其论文的第 5 节中给出了分段版本原纸。大概是伯恩斯坦的primegen程序使用该方法。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

阿特金分段筛可能吗? 的相关文章

  • 对二进制二维矩阵进行排序?

    我在这里寻找一些指示 因为我不太知道从哪里开始研究这个 我有一个二维矩阵 每个单元格中有 0 或 1 例如 1 2 3 4 A 0 1 1 0 B 1 1 1 0 C 0 1 0 0 D 1 1 0 0 我想对其进行排序 使其尽可能 上三角
  • 如何生成排列?

    我的问题是 给定一个长度为 n 的列表 L 和一个整数 i 使得 0 对于任意 i 和任意 2 个列表 A 和 B perm A i 和 perm B i 都必须将 A 和 B 的第 j 个元素映射到 A 和 B 相同位置的元素 对于任何输
  • 比 in_array 更快?

    我需要将一个值与一组数组进行比较 但是 我需要比较 foreach 中的多个值 如果使用 in array 它可能会很慢 非常慢 有没有更快的替代方案 我当前的代码是 foreach a as b in array b array 谢谢 你
  • 算法 - 如何有效删除列表中的重复元素?

    有一个list L 它包含以下元素任意类型each 如何有效删除此类列表中的所有重复元素 必须保留订单 只需要一个算法 因此不允许导入任何外部库 相关问题 在Python中 从列表中删除重复项以使所有元素都是唯一的最快算法是什么在维持秩序的
  • Python:for 循环 - for i in range(0,len(list) 与 for i in list

    这是一个非常简单的Python 力学问题 为什么我不能只说 for i in range original list 而不是 for i in range 0 len original list 人们通常使用范围而不是前者吗 谢谢 If I
  • 识别鼠标移动的算法

    我想知道是否有任何研究 算法可以指定鼠标在识别 等字符时的偏差量使用鼠标绘制 某种光学字符识别 但可能是一个更简单的版本 是否有某种算法可以让我说用户绘制的问号确实是一个问号 而不是其他具有一定准确性的东西 就像 Windows 平板电脑软
  • Python 中的空填字游戏求解器

    我得到了一个包含填字游戏蓝图的矩阵 当然 它是空的 我们的目标是填补整个难题 这是 Checkio 的一项任务 我已经为此奋斗了相当长一段时间 根据我对复杂性的理解 这个问题没有完美的算法 不过 必须有最好的方法来做到这一点 对吧 我尝试了
  • 数组中最远的相等元素

    假设你有一个未排序的数组 你如何找到两个相等的元素 使它们成为数组中最远的元素 例如8 7 3 4 7 5 3 9 3 7 9 0ans 将是7 9 7 1 8 我想到了以下几点 initialise max 0 using hashing
  • 如何在单向链表(一次遍历中)中从尾部获取第 n 个节点?

    所以我在一次考试中得到了这个问题 如何从单链表的尾部获取第 n 个节点 每个节点都有一个值和一个下一个 指向下一个值的指针 我们得到这个 getNodeFromTail Node head int x 所以我的做法是通过遍历一次来求出列表的
  • 运行时间为 O(n) 且就地排序的排序算法

    有没有运行时间为O n 并且还分类到位 在某些情况下 最好的情况是 O n 但这可能是因为项目集合已经排序 你正在看 O nlogn 一些较好的平均值 话虽如此 排序算法的 Wiki 还是相当不错的 有一个表格比较了流行的算法 说明了它们的
  • 更合适地说插入未排序动态数组的摊销 O(1) 与 O(n) ?

    这属于 stackoverflow com help on topic 中的 软件算法 在本例中 是一种将项目添加到动态未排序数组的软件算法 This is chart we made in class about the runtimes
  • 处理流星中的长服务器端计算

    我正在使用 jimp https www npmjs com package jimp https www npmjs com package jimp 在meteor JS中生成图像服务器端 换句话说 我正在使用递归算法 计算 图像的像素
  • Python Pandas:沿一列比较两个数据帧,并返回另一个数据帧中两个数据帧的行内容

    我正在处理两个 csv 文件并作为数据框 df1 和 df2 导入 df1 有 50000 行 df2 有 150000 行 我想将 df2 的 时间 与 df1 求时间差并返回所有列的值 对应相似的行 保存在df3中 时间同步 例如 35
  • 分而治之算法找到两个有序元素之间的最大差异

    给定一个整数数组 arr 找出任意两个元素之间的差异 使得较大的元素出现在 arr 中较小的数字之后 Max Difference Max arr x arr y x gt y 例子 如果数组是 2 3 10 6 4 8 1 7 那么返回值
  • 什么是“朴素”算法,什么是“封闭式”解决方案?

    我有一些关于描述算法时使用的术语语义的问题 首先 朴素 算法是什么意思 这与给定问题的其他解决方案有何不同 解决方案还可以采取哪些其他形式 其次 我听到很多人提到 封闭式 解决方案 我也不知道这意味着什么 但在尝试解决递归关系时经常会出现
  • heapq.nlargest 的时间复杂度是多少?

    我在看演讲者说 获得t列表中最大的元素n元素可以在O t n 这怎么可能 我的理解是创建堆将是O n 但是复杂度是多少nlargest本身就是O n t or O t 实际的算法是什么 在这种情况下 说话者是错误的 实际成本是O n log
  • 如何在C中实现带连分数的自然对数?

    这里我有一个小问题 根据这个公式创建一些东西 这就是我所拥有的 但它不起作用 弗兰基 我真的不明白它应该如何工作 我尝试用一 些错误的指令对其进行编码 N 是迭代次数和分数部分 我认为它会以某种方式导致递归 但不知道如何 谢谢你的帮助 do
  • 为什么这个算法的Big-O复杂度是O(n^2)?

    我知道这个算法的大O复杂度是O n 2 但我不明白为什么 int sum 0 int i 1 j n n while i lt j sum 即使我们设定了j n n一开始 我们在每次迭代期间递增 i 并递减 j 因此最终的迭代次数不应该比n
  • 求先递增后递减列表的最大值和最小值

    我尝试用谷歌搜索这个问题 但没有取得太大成功 我确信这个问题或类似问题有一个技术名称 但我似乎找不到答案 给定一个列表L整数 即严格递增 然后严格递减 找到该列表的最大值和最小值 例如 L可能 1 2 3 4 5 4 3 2 or 2 4
  • 如何计算 3D Morton 数(交织 3 个整数的位)

    我正在寻找一种快速计算 3D Morton 数的方法 这个网站 http www graphics stanford edu seander bithacks html InterleaveBMN有一个基于幻数的技巧来处理 2D Morto

随机推荐