问题标签 [primes]

在我开始自己写这篇文章之前，有没有人看过以下行为的 ruby​​ 实现？

显然，这种事情对于大数来说是丑陋的，但对于从不超过几千的整数（对我来说是常见的例子），一个明智的实现是可行的，因此是个问题。

我学校的计算机科学系报纸（称为自述文件，挪威语，第 19 页）举办了一场有趣的比赛，为以下问题编写尽可能短的 Java 代码。

取一个整数（作为字符串数组的第一个条目中的字符串，因为 Java main 方法只接受一个字符串数组）作为参数，并首先写出该数字以下的所有素数，然后写出所有不是素数。最短的代码获胜！

作为答案，我将发布赢得比赛的最短 Java 代码。我想知道 Stack Overflow 社区是否可以制作更短的代码如果你懂挪威语，你会发现如果你这样做了，你可能会赢得一瓶香槟，但不幸的是，比赛的最后提交日期已经结束。

你会如何解决这个问题？

在 ML 中，我想得到一个数字的主要除数。我该怎么做，我是初学者。

我是 C# 的新手。如果用户在文本框中输入任何整数，我想编写类似的程序，在列表框中显示素数。（这意味着，如果他们写 10，它将显示 0-10 的素数，或 0-20 的 20 等）。

在进行编程之前，我应该首先考虑什么？我知道互联网上有很多例子，但首先我想知道我需要什么？

谢谢你的提示;-）

=== 谢谢大家。所以您建议最好先在控制台应用程序中执行此操作？我使用控制台应用程序做了一个非常简单的“For Loop”示例，但是当我尝试在 Windows 窗体应用程序中执行此操作时，我不确定如何实现它。恐怕如果我继续在控制台中做示例，那么我将很难在 Windows 窗体应用程序中做到这一点。你怎么看？

====== 再次您好，

我需要一些关于我的代码的反馈：

所以我正在研究一种懒惰地生成素数的方法，我想出了这三个定义，它们都以等效的方式工作 - 只是检查每个新整数是否在所有前面的素数中都有一个因子：

所以在我看来primes2应该比 快一点primes1，因为它避免了 f_ = f (const True)对每个整数重新计算（我认为这需要按照我们迄今为止找到的素数数量的顺序工作），并且只在遇到新的时更新它主要。

仅从不科学的测试（take 1000在 ghci 中运行）看来，它的运行速度似乎primes3比primes2.

我是否应该从中吸取教训，并假设如果我可以将函数表示为数组上的操作，我应该以后一种方式实现它以提高效率，还是这里发生了其他事情？

如何通过 C++ 中的位运算找到素数？

有一种简单的密码可以将数字转换为 . ( )

为了将数字（0 .. 2147483647）加密为这种表示，我（认为我）需要：

• 质因数分解
• 对于给定的p（p是 Prime ）， p 的顺序序列（即PrimeOrd(2) == 0，PrimeOrd(227) == 49）

一些例子

我的问题源代码

问题是程序 PrimeOrd 的缓慢性。你知道一些更快的解决方案来找出素数中的素数顺序吗？

标题

如果您知道如何加快查找素数的顺序，请提出一些建议。:-)

谢谢你。

PS 小于 2,147,483,648 的最大素数是2,147,483,647，它是第105,097,565 个素数。没有必要期望比 2^31 更大的数字。

我一直致力于解决Clojure 中的Project Euler问题以变得更好，并且我已经遇到过几次素数生成问题。我的问题是它需要的时间太长了。我希望有人可以帮助我找到一种有效的方法来以 Clojure-y 方式执行此操作。

当我用拳头做这件事时，我是蛮力的。这很容易做到。但是在 Xeon 2.33GHz 上以这种方式计算 10001 个素数需要 2 分钟，这对于规则来说太长了，而且总体上也太长了。这是算法：

通过将 next-prime-slow 替换为新的例程，该例程考虑了一些额外的规则（如 6n +/- 1 属性），我能够将速度提高到大约 70 秒。

接下来，我尝试在纯 Clojure 中制作一个 Eratosthenes 筛子。我不认为我把所有的错误都解决了，但我放弃了，因为它太慢了（我认为甚至比上面的还要糟糕）。

这是不好的。如果数字 150000 更小，它也会导致堆栈溢出。尽管我正在使用 recur。那可能是我的错。

接下来我尝试了一个筛子，在 Java ArrayList 上使用 Java 方法。这需要相当多的时间和记忆。

我最近的尝试是使用 Clojure 哈希映射的筛子，将所有数字插入筛子中，然后分解非素数的数字。最后，它获取密钥列表，这是它找到的素数。找到 10000 个素数大约需要 10-12 秒。我不确定它是否已完全调试。它也是递归的（使用递归和循环），因为我想成为 Lispy。

因此，对于这些问题，问题 10（总结 2000000 以下的所有素数）正在杀死我。我最快的代码给出了正确的答案，但它花了 105 秒，并且需要相当多的内存（我给它 512 MB 只是为了不用大惊小怪）。我的其他算法花了很长时间，我总是先停止它们。

我可以使用筛子快速计算 Java 或 C 中的许多素数，而无需使用太多内存。我知道我的 Clojure/Lisp 风格中一定遗漏了一些导致问题的东西。

我做错了什么吗？Clojure 在处理大序列时会有点慢吗？阅读一些 Euler 项目的讨论，人们在 100 毫秒内计算了其他 Lisps 中的前 10000 个素数。我意识到 JVM 可能会减慢速度，而且 Clojure 相对年轻，但我不希望有 100 倍的差异。

有人可以告诉我在 Clojure 中计算素数的快速方法吗？

（C#，prime generator）这里有一些代码，我和一个朋友正在四处寻找：

在我笨拙的 AMD x64 1800+（双核）上，所有质数低于 10 亿的质数在 34546.875 毫秒内。问题似乎是在位数组中存储更多。试图增加超过 20 亿的数据比 bitarray 想要存储的要多。关于如何解决这个问题的任何想法？

我目前正在做一个项目，我需要一种有效的方法来计算素数。我使用过Eratosthenes 的筛子，但我一直在四处寻找，发现Atkin 的筛子是一种更有效的方法。我发现很难找到这种方法的解释（我已经能够理解！）。它是如何工作的？示例代码（最好是 C 或 python）会很棒。

编辑：感谢您的帮助，我唯一仍然不明白的是伪代码中 x 和 y 变量所指的内容。有人可以为我解释一下吗？