问题标签 [primes]

这不是作业，我只是好奇。

INFINITE 是这里的关键词。

我希望将其用作for p in primes(). 我相信这是 Haskell 中的一个内置函数。

所以，答案不能像“做个筛子”那样天真。

首先，你不知道会消耗多少个连续素数。好吧，假设你一次可以炮制 100 个。您会使用相同的筛法以及素数频率公式吗？

我更喜欢非并发方法。

感谢您阅读（和写作；））！

我是Scheme的新手。我已经尝试并使用 PLT Scheme 实现了 Rabin-Miller 算法的概率变体。我知道这是概率性的，但我大部分时间都得到错误的结果。我用 C 实现了同样的东西，而且效果很好（从来没有失败过）。我在调试时得到了预期的输出，但是当我运行时，它几乎总是返回错误的结果。我使用了来自Wikipedia的算法。

另外，我是否在 Scheme 中以正确的方式编程？（我不确定我使用的循环部分的中断call/cc。我在某个网站上找到了它，从那以后一直在使用它。）

提前致谢。

有没有一种直接的方法可以仅使用按位运算从 2 的幂中提取指数？

编辑：虽然这个问题最初是关于按位运算的，但如果您想知道“在 Python 中给定 Y = 2 X找到 X 的最快方法是什么？”**

我目前正在尝试优化一个减少表单中偶数N的例程（ Rabin-Miller primality test ） 。我可以通过以下方式获得零件：2**s * d2**s

但我找不到通过按位运算仅提取“ s ”的方法。我目前正在测试的解决方法不太满意（它们都非常慢）是：

• 使用对数函数
• 操作 2**s 的二进制表示（即计算尾随零）
• 循环除以 2 直到结果为 1

我正在使用 python，但我想这个问题的答案应该与语言无关。

“计算第n个素数”的最短C 代码是什么？

就重要字符而言最短，即分号、非空白字符、关键字和逗号的数量。

输入：

来自标准输入的整数n，由新行分隔。输入将由 EOF 终止。

输出：

在输入n之后，将第n个素数打印到由新行分隔的标准输出。

（您可以假设素数 < 10,000，即n < 1,230。）

测试用例：

我的尝试：

对于这个问题，可读性不是问题。在时间和内存方面成本更高但满足约束的代码在这里会被认为更好。

Need a suggestion for an algorithm.

For a given number N i have to find all the prime numbers it's consisting of, like this:

If you want to help me even more you can write the algo in c++.

Thanks.

我一直在尝试编写一个程序来确定一个数字是否是素数。我的基础是埃拉托色尼筛法。无论如何，我的程序适用于小数字（15485863 有效），但如果我使用大数字（例如 17485863），我会收到分段错误。我正在使用 unsigned long longs 并且不认为我已经超过了它们的最大值。我只是不明白我做错了什么。提前感谢您的任何帮助！

我是一名大学生，有一项需要找到大素数的作业。教授给了我以下“简单”算法，以找到 2 个可能的素数。

1. 生成随机 a 和 p 其中 1 < a < p
2. 确认 gcd(a,p) 是 = 1 - 这是假设删除 Carmichael 数字编辑（意味着等于 1）
3. 如果 x ^ (p-1) % p = 1 则执行“模幂运算”，其中 x 从零开始，对于 p 和 a 都递增到 p-1

第三步的例子。

假设 p = 5

1^4 %5 = 1

2^4 %5 = 1

3^4 %5 = 1

4^4 %5 = 1

这表明 5 是素数。

我通过这个作业意识到计算素数不是开玩笑。我在上述算法中看到的问题是，如果我猜测大数并使用模幂来测试它们，我可能会尝试将大数提升为大数。这让我心中产生了疑问。我也研究了确定性有限自动机和埃拉托色尼筛法。有没有人有任何建议来改进给定的算法或提供任何帮助？谢谢你的时间。

我试图找到检查给定数字是否为素数的最快方法（在Java中）。以下是我想出的几种素性测试方法。有没有比第二种实现（isPrime2）更好的方法？

我对阿特金筛法的实现要么忽略了接近极限的素数，要么忽略了接近极限的复合物。有些限制有效，有些则无效。我对出了什么问题感到完全困惑。

例如，当我生成一个限制为 1000 的素数时，阿特金筛漏掉了素数 997，但包括了复合 965。但是如果我生成了 5000 的限制，它返回的列表是完全正确的。

我正在尝试制作一个程序来确定数字是素数还是合数。到目前为止，我已经得到了。你能给我一些想法让它起作用吗？但是，所有素数都会 ，因为复合物的值都是 r>0 和 r==0，所以它们总是被归类为素数。我怎样才能解决这个问题？