问题标签 [sieve-of-eratosthenes]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
4071 浏览

c - C中的埃拉托色尼筛算法

好的,所以我创建的这个函数使用 Eratosthenes 算法来计算所有素数 <= n。该函数在参数中存储素数和素数。

当函数退出时,素数应该指向一块动态分配的内存,其中包含所有素数<= num。 *count将有素数的计数。

这是我的功能getPrimes

现在,这是预期的输出和我的输出。如您所见,我的getPrimes功能中有问题,但我不确定是什么。

到目前为止,人们向我指出了以下 3 个问题:

  1. 错误的删除过程if (sieve[multiple]) {数组筛子索引有偏差
  2. (*array) = sieve;泄漏刚刚分配的内存,并让我们*array指向一个在函数返回时不再存在的局部变量——你会得到一个悬空指针。
  3. if(sieve[i] != NULL)应该使用 0,而不是 NULL,你没有指针数组。

但是,我不太确定如何解决已为我发现的悬空指针/内存问题。除此之外,我想知道我的代码中是否还有其他错误,因为我不太清楚为什么我的输出中的数字添加了 0...不要担心不同的输出样式,只是额外的数字. 谢谢你能帮我解决这个问题!

0 投票
1 回答
322 浏览

c - C中的埃拉托色尼筛算法的分割错误

好的,所以我创建的这个函数使用 Eratosthenes 算法来计算所有素数 <= n。该函数在参数中存储素数和素数。

当函数退出时,素数应该指向一块动态分配的内存,其中包含所有素数<= num。*count 将有素数的计数。

这是我的函数 getPrimes:

我的函数在这里编译得很好,但是我注意到当我尝试从 101 开始的更大数字时出现分段错误。有谁看到我的代码在哪里产生分段错误?

0 投票
2 回答
58 浏览

c - 第一个案例整数的奇怪输出

下面是两个可以完美编译的函数,但我似乎在第一个输入的整数时遇到了一个奇怪的错误。我已经尝试在 GDB 中进行调试,但是当只有第一个输入值出现这个奇怪的错误时,它会让事情变得复杂。

我们的输出:

预期的输出显然应该只显示 2。对于第一个输入的整数,从 2 到 2000 的任何整数都是这种情况。最后一个或最后 2 个素数打印非常大的数字,有时甚至是负数。我不知道为什么,但是在第一个输入值之后一切正常。疯狂地尝试用 GDB 调试它,但没有运气。非常感谢有人对这个奇怪的错误的帮助

0 投票
4 回答
758 浏览

c++ - 埃拉托色尼筛法实施

我正在尝试为埃拉托色尼筛法实现算法,但我不知道为什么该程序会因较大的程序而崩溃。最初我正在使用vector,但现在我正在使用动态内存分配来实现它。

n程序因和m(~10^16)的较大值而崩溃。请帮帮我。

0 投票
2 回答
18445 浏览

python - Python 中的快速素数筛

我一直在使用 Eratosthenes 的筛子在 python 中生成素数,人们吹捧为相对较快的选择的解决方案,例如 关于在 python 中优化素数生成的问题的一些答案中的解决方案并不简单,而且我在这里的简单实现在效率上与它们相媲美。我的实现如下

定时执行返回

虽然上面链接问题的答案中描述的方法是python食谱中最快的方法,但下面给出

运行时它给出

我的问题是,为什么人们会从相对复杂的烹饪书中吹捧上述内容作为理想的素数发生器?

0 投票
5 回答
17598 浏览

python - 在 Python 中对数字进行因式分解

这是我的代码:

factorize(n)返回给定值的所有素因子n。如您所见,它首先nn. 它为此目的工作相对较好,但是,我希望它返回一个列表,这样如果您将其中的每个项目相乘,结果就是n. 你明白我的意思吗?

例如,factorize(99020)返回[2, 5, 4951],但我希望它返回[2, 2, 5, 4951],如2*2*5*4951 = 99020

我知道我的方法还不够接近,但你能帮我做到吗?

0 投票
1 回答
776 浏览

c - 使用位数组筛选 Eratosthenes

我有prime[]一些unsigned int. 我希望使用这个数组来实现一个埃拉托色尼筛,让每个位代表一个数字n。也就是说,在给定的情况下n,包含对应的位的数组元素n将是prime[n/32],并且特定位将在位置n%32

testBitIs0(int n)当数字为素数时(如果它的位 == 0), 我的函数返回 1,否则返回 0:

我的setBit(int n)函数只是将相应位置的位设置为 1:

我遇到的问题是,当我setBit使用多个素数调用时,我认为它设置的位不正确。下次运行此行时,当我setBit使用质数的倍数(例如数字 2 的 4、6、8 等)调用时:

i = 4/6/8/etc它应该返回 0 时它仍然会返回 1。
有人可以检查我的代码以确保我正确地实现它吗?谢谢。

0 投票
2 回答
21721 浏览

matlab - 如何使用 Eratosthenes 的筛子编写列出素数的函数

我应该编写一个函数或脚本,使用“Eratosthenes 筛”找到所有小于给定整数 n>2 的素数 p,从而避免不必要的存储(我可以创建长度为 n 但不能更多的向量)

我意识到这与我应该编写的代码相去甚远。但这是我想到的唯一想法,它只删除可被 2 和 3 整除的数字,我需要通过对每个条目重复此操作来找到所有素数。这显然不聪明。但我觉得可以为此创建一个循环。但我没有编写这个循环。请帮忙。

0 投票
4 回答
805 浏览

python - 这比埃拉托色尼筛法更有效吗?

我在 Python 2.7 中编写了一个用于创建素数列表的代码。代码是

这是否比埃拉托色尼筛法更有效?我认为内存效率应该更好,但我对时间效率表示怀疑。如何计算时间和内存效率以及如何对效率进行基准测试?

0 投票
3 回答
867 浏览

c++ - 运行时错误 (SIGSEGV) SPOJ 埃拉托色尼筛

嗨,我收到此问题的 SIGSEGV 错误,不知道问题出在哪里: http ://www.spoj.com/problems/PRIME1/ 我试图通过 Wikipedia 上给出的 sieve-of-Eratosthenes 算法来解决它。这是我的代码,请帮助提前谢谢。