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

发布于 2024-10-01 22:22:35 字数 982 浏览 4 评论 0原文

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

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

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

感谢你们所有人

提前

沙恩沙

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

I want to make library classes in Java and use them in my future programs. I want these library classes to find prime numbers upto a certain number or even the next prime number or you can say solve most of the basic things related to prime numbers.

  1. I have never made a Java Library Class. I aim to learn that doing this. Please help me without that by pointing out a tutorial or something. I am familiar with netbeans IDE.
  2. I found out a few algorithms like Sieve of Eratosthenes and Sieve of Atkin. It would be great if you can point out a few more such efficient algorithms. I don't want them to be the best but at least good enough. My aim is to learn few things by implementing them. Because I have little practical coding experience I want to do it to improve my skills.
  3. My friend suggested me to use Stream Classes and he was talking something about implementing it by giving the output of one file as an input to another to make my code clean. I didn't understand him very well. Please pardon me if i said anything wrong. What I want to ask in this point is, is that an efficient and OO way of doing what i want to do. If yes please tell me how to do that and if not please point out some other way to do it.

I have basic knowledge of the Java language. What I want to accomplish through this venture is gain coding experience because that is what everyone out here suggested, "to take up small things like these and learn on my own"

thanks to all of you in advance

regards

shahensha

EDIT:
In the Sieve of Eratosthenes and others we are required to store the numbers from 2 to n in a data structure. Where should I store it? I know I can use a dynamic Collection, but just a small question...If i want to find primes in the order of billions or even more (I will use Big Integer no doubt), but all this will get stored in the heap right? Is there a fear of overflow? Even if it doesn't will it be a good practice? Or would it be better to store the numbers or the list (on which we will perform actions depending on the algorithm we use) in a file and access it there? Sorry if my question was too noobish...

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

羁〃客ぐ 2024-10-08 22:22:35

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

"Sieve of Eratosthenes" is good algorithm to find the prime numbers. If you will use google you can find ready implementation in java.

我将对此添加一些想法:

  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);

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

I'll add some thoughts to this:

  1. There's nothing technically different about a Library Class, it's simply how you use it. To my mind, the most important thing is that you think hard about your public API. Make it bit enough to be useful to your prospective callers, keep it small enough that you have freedom to change the internal implementation as you see fit, and ensure that you have a good understanding of what your library does do and what it doesn't do. Don't try to do everything, just do one thing well. (And the API generally extends to documentation too, make sure you write decent Javadocs.)
  2. Start with either of these as they are fine. If you design your API well, you can change this at any time and roll out version 1.1 that uses a different algorithm (or even uses JNI to call a native C library), and your callers can just drop in the new JAR and use your code without even recompiling. Don't forget that premature optimisation is the root of all evil; don't worry to much about making your first version fast, but focus on making it correct and making it clean.
  3. I'm not sure why your friend was suggesting streams. Streams are a way of dealing with input and output of raw bytes - useful when reading from files or network connections, but generally not a good way to call another Java method. Your library shouldn't worry about input and output, it just needs to offer some methods for numerical calculations. So you should implement methods that take integers (or whatever is appropriate) and return integers.

For instance, you might implement:

/**
 * 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);

No streams in sight! Uses of streams, such as outputting to the console, should be handled by applications that use your library and not by your library itself. This is what I meant in my first point about being clear of what your library does and doesn't do. You just generate the prime numbers; it's up to the caller to then do something cool with them.

诠释孤独 2024-10-08 22:22:35

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

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

祝你好运..

But when you compare, the sieve of Atkin is faster than the sieve of Eratosthenes:

http://en.wikipedia.org/wiki/Prime_number_counting_function Also refer to this link where different functions are explained clearly :)

Good luck..

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

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

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

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

  1. There is no such thing as "library class". I suppose you mean to make a class in such a way that does it's job in a reusable way. The way to do this is to have a clean interface - with minimal (if any) bindings to other libraries or to your execution environment (your main class etc).

  2. The two you mention are "good enough". For your purpose you don't need to look any further.

  3. Just read from System.in and write to System.out and that's it. Though, in your case, there is nothing to read.

To achieve what I think is your goal, you need to write a main class that hadles the execution environment - main function, initialize your algorithm, iteratively look for the next prime, and write it to System.out. Of course, you'll need another class to implement the algorithm. It should contain the internal state and provide a method for finding the next prime.

凉月流沐 2024-10-08 22:22:35

`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 标记问题。

希望这会有所帮助。

`IMO, keep aside the thought that you're making a library (.jar file according to my interpretation of this question).

Focus on creating a simple Java class first, like this:

//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);
}
}

Now, the next step; Implementing it for larger values, you can always use BigInteger. SO questions pertaining to the same:

  1. Java BigInteger Prime numbers
  2. Problems with java.math.BigInteger
  3. BigNums Implementation

Try reading all questions related to BigInteger class on SO, BigInteger Tagged questions.

Hope this helps.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文