阿特金分段筛可能吗?

2023-11-23

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

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

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

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


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

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

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

  • 合并空间上接近的路径/线段的算法

    我正在寻找一种用于街道地图制图概括的几何算法 名称 在我的地图数据中 我有许多路径 点的有序列表 由线段连接 这些路径彼此靠近且几乎平行 我如何 1 识别这些 相邻路径 即如何找到比某个阈值更接近的路径 以及 2 将它们合并成一条路径 即如
  • 优雅的折线“左移”测试

    Given X Y 坐标 即车辆的位置 X Y 数组 它们是折线中的顶点 请注意 折线仅由直线段组成 没有圆弧 我想要的是 计算车辆是在折线的左侧还是右侧 当然还是在顶部 我的做法 迭代所有线段 并计算到每个线段的距离 然后 对于最近的段
  • 修改排列算法以防止重复打印输出的策略

    我一直在审查实践算法 目前正在研究一种我非常喜欢的排列算法 void permute char set int begin int end int range end begin if range 1 cout lt lt set lt l
  • 获取无平方数的列表

    获得该值的一种方法是自然数 1 n 我们对每个因子进行因式分解 看看它们是否有重复的质因数 但这对于大的情况来说会花费很多时间n 那么有没有更好的方法从 1 中获取无平方数n 您可以使用埃拉托斯特尼筛法的修改版本 取一个布尔数组 1 n 预
  • C# 计算LRC(纵向冗余检查)

    我一直在到处研究这个问题 所有 LRC 实现似乎都没有给我正确的答案 花了几天时间后 我决定将我的代码放在这里 看看其他人是否可以发现问题 这是代码 C Input Data 31303030315E315E31303030325E315E
  • 用于插入/删除/排名/选择查询的最佳数据结构/算法

    到目前为止 我知道像AVL树和红黑树这样的自平衡BST可以在O log n 次内完成这些操作 然而 要使用这些结构 我们必须自己实现AVL树或RB树 我听说有一个算法 实现这四个操作而不使用自平衡 BST 有了我们自己定义的结构 我们就需要
  • 基于时间的算法评分

    我们希望创建一种评分算法 在更短的时间内获得更高的分数 在更长的时间内获得更少的分数 需要注意的是 没有实际范围 因此时间范围可以从 100 毫秒到长达 10 分钟或更长时间 点范围为 0 到 50 谢谢你的帮助 你可以简单地把它变成一个线
  • C 中的菱形数组排序

    我有以下 C 语言作业 我基本上需要一种方法而不是解决方案 我们有一个 13 x 13 的数组 在数组中 我们有一个需要考虑的菱形形状 该菱形之外的所有内容都初始化为 1 不重要 下面的 5 x 5 数组示例 x x 1 x x x 2 2
  • Exposé 布局算法

    我正在制作一些项目 其布局类似于 Mac OS X 在 Expos 中对窗口所做的操作 它适应项目的长宽比和可用区域的长宽比 基本上 可用区域分为行和列 每个单元格 行和列的交集 中放置一个项目 这些项目必须保持其纵横比 此处width h
  • 在 Java 中实现排列算法的技巧

    作为学校项目的一部分 我需要编写一个函数 该函数将接受整数 N 并返回数组 0 1 N 1 的每个排列的二维数组 该声明看起来像 public static int permutations int N 该算法描述于http www usn
  • 使用FFT算法计算

    给定在平面上的点 1 0 2 0 n 0 上发现的一组 n 个粒子电荷载流子 在 i 0 点发现的粒子电荷记为 Qi 作用在粒子上的力由以下公式给出 C is a Coulomb s constant 给出一个算法来计算 Fi 对于总复杂度
  • 在 O(n) 时间内找到 n x n 矩阵中的局部最小值

    所以 这不是我的家庭作业问题 而是取自 coursera 算法和数据结构课程的未评分作业 现已完成 You are given an n by n grid of distinct numbers A number is a local m
  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d
  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要
  • 如何确定算法函数的复杂度?

    您如何知道算法函数对于特定操作是否需要线性 常数 对数时间 它取决于CPU周期吗 您可以通过三种方式 至少 做到这一点 在网上查找算法 看看它是如何描述其时间复杂度的 根据输入大小 自己检查算法 查看嵌套循环和递归条件等内容 以及每个循环运
  • 最慢的计算复杂度(Big-O)

    在这些算法中 我知道 Alg1 是最快的 因为它是 n 平方的 接下来是 Alg4 因为它是 n 的立方 然后 Alg2 可能是最慢的 因为它是 2 n 这应该具有非常差的性能 然而Alg3和Alg5在我的阅读速度方面还没有遇到过 这两种算
  • 解释一下从 N 个给定集合中的每一个中给出第 K 个最大数字的示例?

    今天我尝试解决一个Facebook 编程挑战赛 https facebook interviewstreet com recruit challenges 我遇到的挑战是 酒吧问题 可以找到here https github com alo
  • 如何求小于给定数的最大2次方

    我需要找到小于给定数字的最大 2 次幂 我陷入困境 找不到任何解决方案 Code public class MathPow public int largestPowerOf2 int n int res 2 while res lt n
  • 有人可以解释以下异或属性

    我的一个论坛提到给定的数组n数字 arr 0 n 1 以下条件成立 is the xor运算符 f l r f 0 r f 0 l 1 where f l r arr l arr l 1 arr r 我检查了上面的数组数量和不同的值l an
  • Karasuba算法递归过多

    我正在尝试用 c 实现 Karasuba 乘法算法 但现在我只是想让它在 python 中工作 这是我的代码 def mult x y b m if max x y lt b return x y bm pow b m x0 x bm x1

随机推荐