在Java中实现质数查找算法的最佳方法是什么？我们如何制作库类并在Java中使用它们？

Question

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

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

我有Java语言的基本知识。我想通过这次冒险获得的是编码经验，因为这里的每个人都建议，“学习这些小东西，自己学习”

提前感谢大家

问候

沙恩沙

编辑： 在Eratosthenes和其他人的筛选中，我们需要在数据结构中存储从2到n的数字。我应该把它存放在哪里？我知道我可以使用动态收藏，但只是一个小问题。。。如果我想找到数十亿甚至更多的素数（毫无疑问，我会使用大整数），但所有这些都会存储在堆中，对吗？是否担心溢出？即使没有，这是否是一个良好的做法？或者将数字或列表（我们将根据使用的算法对其执行操作）存储在一个文件中并在那里访问会更好吗？对不起，如果我的问题太离谱

Answer 1

但当你比较时，阿特金的筛子比埃拉托斯坦的筛子快：

http://en.wikipedia.org/wiki/Prime_number_counting_function也可参考此链接，其中清楚地解释了不同的功能：）

祝你好运

Answer 2

1. 没有“图书馆类”这样的东西。我想您的意思是以一种可重用的方式创建一个类。实现这一点的方法是拥有一个干净的接口——与其他库或执行环境（主类等）的绑定最少（如果有的话）

2. 你提到的两个“足够好”。为了你的目的，你不需要再看下去了

3. 从系统中读取。输入并写入系统。出去，就这样。不过，就你而言，没有什么可读的

为了实现我认为是您的目标，您需要编写一个包含执行环境的主类—main函数，初始化算法，迭代查找下一个素数，并将其写入系统。出来当然，您需要另一个类来实现该算法。它应该包含内部状态，并提供查找下一个素数的方法

Answer 3

“依我看，别再想你在建一个库了。根据我对这个问题的解释，是（.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 Prime numbers
2. Problems with java.math.BigInteger
3. BigNums Implementation

试着在SO上阅读所有与BigInteger类相关的问题BigInteger Tagged questions.

希望这有帮助

Answer 4

我将补充一些想法：

1. 图书馆类在技术上没有什么不同，只是你如何使用它。在我看来，最重要的是你认真考虑你的公共API。使其足够小，以便对潜在的调用方有用，使其足够小，以便您可以根据自己的需要自由更改内部实现，并确保您很好地了解库的功能。不要试图做每件事，只要把一件事做好。（而且API通常也扩展到文档，请确保编写体面的Javadocs。）
2. 从它们中的任何一个开始，因为它们都很好。如果您的API设计得很好，您可以随时更改它，并推出使用不同算法（甚至使用JNI调用本机C库）的1.1版，您的调用者只需插入新的JAR即可使用您的代码，而无需重新编译。不要忘记，过早的优化是万恶之源；不要太担心让你的第一个版本快速，但要专注于使它正确和干净
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 5

“Eratosthenes筛法”是寻找素数的好算法。如果你使用谷歌，你可以找到ready implementation in java