在 Java 中实现素数查找算法的最佳方法是什么？我们如何创建库类并在Java中使用呢？

Question

我想用 Java 制作库类并在我未来的程序中使用它们。我希望这些库类能够找到达到某个数字甚至下一个素数的素数，或者您可以说解决与素数相关的大多数基本问题。

1. 我从未制作过 Java 库类。我的目标是学习这样做。如果没有，请通过指出教程或其他东西来帮助我。我熟悉netbeans IDE。
2. 我发现了一些算法，例如 Eratosthenes 筛法 和 阿特金筛。如果您能指出更多这样的高效算法，那就太好了。我不希望他们成为最好的，但至少足够好。我的目标是通过实施它们来学到一些东西。因为我几乎没有实际编码经验，所以我想通过这样做来提高我的技能。
3. 我的朋友建议我使用流类，他正在谈论通过将一个文件的输出作为另一个文件的输入来实现它，以使我的代码干净。我不太了解他。如果我说错了什么请原谅我。在这一点上我想问的是，这是一种高效且面向对象的方式来做我想做的事情。如果是，请告诉我如何做到这一点，如果不是，请指出其他方法。

我有 Java 语言的基础知识。我想通过这次冒险来实现的是获得编码经验，因为这是这里每个人的建议，“从这些小事情开始自己学习”

感谢你们所有人

提前

沙恩沙

编辑： 在埃拉托斯特尼筛法和其他筛法中，我们需要将 2 到 n 的数字存储在数据结构中。我应该把它存放在哪里？我知道我可以使用动态集合，但只是一个小问题......如果我想找到数十亿甚至更多的素数（毫无疑问我会使用大整数），但所有这些都会存储在堆中正确的？是否担心溢出？即使不是，这也是一个好的做法吗？或者将数字或列表（我们将根据我们使用的算法对其执行操作）存储在文件中并在那里访问它会更好吗？抱歉，如果我的问题太幼稚了......

Answer 1

“埃拉托斯特尼筛法”是寻找素数的好算法。如果您将使用谷歌，您可以找到Java 中的就绪实现。

Answer 2

我将对此添加一些想法：

1. 库类在技术上没有什么不同，只是您如何使用它。在我看来，最重要的是认真考虑你的公共 API。让它足够小，以便对您的潜在调用者有用，保持它足够小，以便您可以自由地更改您认为合适的内部实现，并确保您很好地理解您的库做什么它做什么以及它不做什么。不要试图做好所有事情，只做好一件事。 （API 通常也会扩展到文档，请确保您编写得体 Javadocs。）
2. 从其中任何一个开始，因为它们都很好。如果你的 API 设计得好，你可以随时更改它并推出使用不同算法的 1.1 版本（甚至使用 JNI 调用本机 C 库），并且你的调用者只需放入新的 JAR 并使用你的 API代码甚至无需重新编译。不要忘记过早的优化是万恶之源；不要太担心如何使您的第一个版本快速，而是专注于使其正确并使其干净。
3. 我不确定你的朋友为什么建议流。流是一种处理原始字节输入和输出的方法 - 从文件或网络连接读取时很有用，但通常不是调用其他 Java 方法的好方法。你的库不应该担心输入和输出，它只需要提供一些数值计算的方法。因此，您应该实现采用整数（或任何适当的方法）并返回整数的方法。

例如，您可以实现：

/**
 * Calculates the next prime number after a given point.
 *
 * Implementation detail: callers may assume that prime numbers are
 * calculated deterministically, such that the efficiency of calling
 * this method with a large parameter is not dramatically worse than
 * calling it with a small parameter.
 *
 * @param x The lower bound (exclusive) of the prime number to return.
 * Must be strictly positive.
 * @return Colloquially, the "next" prime number after the given parameter.
 * More formally, this number will be prime and there are no prime numbers
 * less than this value and greater than <code>x</code> that are also
 * prime.
 * @throws IllegalArgumentException if <code>x</code> is not strictly
 * positive.
 */
public long smallestPrimeGreaterThan(long x);

/**
 * Returns all prime numbers within a given range, in order.
 *
 * @param lowerBound The lower bound (exclusive) of the range.
 * @param upperBound The upper bound (exclusive) of the range.
 * @return A List of the prime numbers that are strictly between the
 * given parameters.  This list is in ascending order.  The returned
 * value is never null; if no prime numbers exist within the given
 * range, then an empty list is returned.
 */
public List<Long> primeNumbersBetween(long lowerBound, long upperBound);

看不到流！流的使用（例如输出到控制台）应该由使用您的库的应用程序处理，而不是由您的库本身处理。这就是我在第一点中的意思，即清楚你的图书馆做什么和不做什么。您只需生成素数即可；然后由调用者来对他们做一些很酷的事情。

Answer 3

但是当你比较时，阿特金筛比埃拉托斯特尼筛更快：

http://en.wikipedia。 org/wiki/Prime_number_counting_function 另请参阅此链接，其中清楚地解释了不同的函数:)

祝你好运..

Answer 4

1. 不存在“库类”这样的东西。我想你的意思是以这样的方式创建一个类，以可重用的方式完成它的工作。做到这一点的方法是拥有一个干净的接口 - 与其他库或执行环境（您的主类等）的绑定最少（如果有）。

2. 你提到的两个“足够好”。出于您的目的，您不需要再进一步寻找。

3. 只需从 System.in 读取并写入 System.out 即可。不过，就您而言，没有什么可读的。

为了实现我认为你的目标，你需要编写一个主类来处理执行环境 - main 函数，初始化你的算法，迭代地寻找下一个素数，并将其写入 System.out。当然，您需要另一个类来实现该算法。它应该包含内部状态并提供寻找下一个素数的方法。

Answer 5

`IMO，不要以为您正在创建一个库（根据我对这个问题的解释，.jar 文件）。

首先专注于创建一个简单的 Java 类，如下所示：

//SieveOfEratosthenes.java
  public class PrimeSieve{
    public static void main(String args[])
    {
    int N = Integer.parseInt(args[0]);
             // initially assume all integers are prime
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {

        // if i is prime, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ..., N/i
        if (isPrime[i]) {
            for (int j = i; i*j <= N; j++) {
                isPrime[i*j] = false;
            }
        }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) primes++;
    }
    System.out.println("The number of primes <= " + N + " is " + primes);
}
}

现在，下一步；如果要实现更大的值，您始终可以使用 BigInteger。与此相关的问题：

1. Java BigInteger素数
2. java.math.BigInteger 的问题
3. BigNums 实现

尝试阅读 SO 上与 BigInteger 类相关的所有问题，BigInteger 标记问题。

希望这会有所帮助。