Which is the best way to implement prime number finding algorithms in Java? How do we make library classes and use then in Java?_问答_开发者

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.

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.
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.
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 m开发者_StackOverflow社区e 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...

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

I'll add some thoughts to this:

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

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..

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).
The two you mention are "good enough". For your purpose you don't need to look any further.
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.

`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: