What is the best way to implement prime search algorithms in Java? How can we create library classes and use them in Java?

Question

I want to make library classes in Java and use them in my future programs. I want these library classes to find primes up to some number or even the next prime number, or you can solve most of the basic things related to primes.

• I have never done a Java library class. I want to know how to do this. Please help me without this by pointing out a textbook or something like that. I am familiar with netbeans IDE.
• I found several algorithms such as Sieve of Eratosthenes and Sieve Atkin . It would be great if you would specify some more such efficient algorithms. I do not want them to be the best, but at least good enough. My goal is to learn a few things by realizing them. Since I have little practical coding experience, I want to do this to improve my skills.
• My friend suggested I use Stream Classes, and he said something about its implementation, providing the output of one file as input to another, to make my code clean. I didn’t understand him very well. Please forgive me if I say something wrong. What I want to ask in this question is that there is an efficient and OO way of doing what I want to do. If yes, please tell me how to do this, and if not, please indicate another way to do this.

I have basic knowledge of the Java language. What I want to achieve through this enterprise is coding experience, because this is what everyone here suggested, "take on such small things and learn on your own"

thanks to all of you in advance

considers

shahensha

EDIT: In the sieve of Eratosthenes and others, we need to store numbers from 2 to n in the 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 prime numbers in billions or more (I will use Big Integer without a doubt), but will all this be stored on the heap correctly? Is there a fear of overflow? Even if this is not good practice? Or would it be better to store numbers or a list (by which we will perform actions depending on the algorithm used) in a file and get access to it? Sorry if my question was too noobish ...

Answer 1

Eratosthenes sieve is a good algorithm for finding prime numbers. If you use Google, you can find a ready-made implementation in java .

Answer 2

I will add the following considerations:

• There is nothing technically different in the library class, just how you use it. In my opinion, the most important thing is that you think a lot about your public API. Make it enough bits to be useful to your potential subscribers, keep it small enough to be able to change the internal implementation of your choice and make sure that you have a good idea of ​​what your library does and does not do . Do not try to do everything, just do one thing. (And the API usually extends to documentation, make sure you write decent Javadocs .)
• Start with any of them as they are in order. If you are designing your API well, you can change it at any time and deploy version 1.1, which uses a different algorithm (or even uses the JNI to invoke your own C library), and your subscribers can just look into the new JAR and use your code without recompiling . Do not forget that premature optimization is the root of all evil; don't worry about making your first version quick, but focus on making it right and keeping it clean.
• I don’t know why your friend was offering streams. Streams - this is a way of processing input and output data of raw bytes - is useful when reading from files or network connections, but, as a rule, is not a good way to call another Java method. Your library does not need to worry about input and output, you just need to offer some methods for numerical calculations. Thus, you must implement methods that accept integers (or something suitable) and return integers.

For example, you can 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! Using streams, such as console output, should be handled by applications using your library, not the library itself. This is what I meant in my first paragraph about being free from what your library does and does not do. You just generate prime numbers; it’s up to the caller to then do something cool with them.

Answer 3

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

http://en.wikipedia.org/wiki/Prime_number_counting_function Also refer to this link for different functions :)

Good luck ..

Answer 4

• There is no such thing as a “library class”. I suppose you want to make the class so that it works 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 runtime (your main class, etc.).

• The two words you mention are good enough. For your purpose, you no longer need to look.

• Just read from System.in and write in System.out and that. Although in your case there is nothing to read.

To achieve what, in your opinion, is your goal, you need to write a main class that has a runtime - the main function, initializes your algorithm, iteratively searches for the next prime and writes it to System.out. Of course, to implement the algorithm you will need a different class. It should contain an internal state and provide a method for finding the next prime number.

Answer 5

ʻIMO, don’t consider that you are creating a library (.jar file according to my interpretation of this question).

Focus on creating a simple Java class first, for example:

 //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; By implementing it for large values, you can always use BigInteger. SO questions related to the same:

• Basic Java BigInteger Numbers
• Problems with java.math.BigInteger
• BigNums implementation

Try to read all the questions related to the BigInteger class on SO, BigInteger with tags.

Hope this helps.