6

情况：

  • 我正在编写一个程序来解决素数。我需要解决 4x^2+y^2=n 的问题，其中 n 是一个已知变量。
  • 是的，它必须是 Ruby。
  • 我很乐意在这个项目上花费大量时间。
  • 我最好自己编写方程的求解算法，并将其作为该项目的一部分。

我真正喜欢的：

  • 如果有人可以向我提供指向与求解代数方程相关的形式算法的构造的指南、网站或消歧的链接，或者向我提供在读者看来这将有助于我的探索的信息。
  • 请不要建议我使用其他语言。如果您在回答之前接受我真的非常想这样做，我也将不胜感激。这个项目没有范围和时间限制，也不是为了盈利。这是为了我自己的教育。

笔记：

  • 我并不直接反对为 Ruby 实现和使用已经存在的数学库/模块/某些东西，但另一种方式对我来说更可取。

结束评论：

问题是我知道如何用手/用计算器解决这些方程，但我不确定如何用代码解决它们。

4

2 回答 2

2

我想你正在实施阿特金筛法。在这种情况下，您实际上并没有求解方程。查看原始论文以了解实际算法。

于 2012-05-08T19:44:35.623 回答
2

看起来您正在尝试实现阿特金筛，那么您可能也知道 4x^2+y^2=n 只是三个方程中的第一个。我不想破坏你的乐趣，因此下面只实现了那个。如果您遇到困难，请评论此答案，我会回复您。

max = 100
primes = Array.new(max + 1) { false }
sqrt = Math.sqrt(max)
1.upto(sqrt) do |x|
  1.upto(sqrt) do |y|
    n = 4 * x**2 + y**2
    primes[n] ^= true if n <= max && (n % 12 == 1 || n % 12 == 5)
  end
end
于 2012-05-08T21:23:25.080 回答