5
\$\begingroup\$

I am trying to implement a method that generates a random prime number between a given range.

I have tried using a simple method to find whether a number is prime or not, advanced simple method, Wilson's method and I ended up with sieve of Eratosthenes as soon as my code based on this algorithm is faster than all of previous methods for finding if a number is prime or not.

Although the efficiency is satisfying, I know that there is an implementation that works without creating an array and with the code run even faster, but I don't know how to do this, so my question is obvious.

import acm.program.*;
import acm.util.RandomGenerator;

public class exercise4 extends Program {
public int nextPrime(int n){                                          //sieve of Eratosthenes
        final RandomGenerator rgen = RandomGenerator.getInstance();
        boolean[] array = new boolean[n];
        for (int i=2; i<n;i++) {
            array[i]=true;
        }
        int i=2;
        while (i<Math.sqrt(n)) {
            if (array[i]==true) {
                int m=i*i;
                int j=0;
                while (m+j*i<n) {
                    array[m+j*i]=false;
                    j++;
                };
            };
            i++;
        };
        int random;
        do {
            random=rgen.nextInt(n);
        } while(array[random]==false);
        return random;
    }
    public void run(){
        //long start = System.currentTimeMillis(); 
        println(nextPrime(2_000_000));
        //long elapsedTimeMillis = System.currentTimeMillis()-start;
        //float elapsedTimeSec = elapsedTimeMillis/1000F;
        //println("Completed in: "+elapsedTimeSec+" seconds.");
    }
}
\$\endgroup\$
2
\$\begingroup\$

I will explicitly answer regarding your sieve and its performance.

Firstly, you should know that you cannot write an implementation of the Sieve of Eratosthenes without an array; that is core to its being.

However, your method of selection can be improved.

First, let us rewrite the sieve in terms of for-loops, since it is more natural to do so. I will also change your implementation from checking primeness to checking compositeness, which avoids the initialization step.

boolean[] isComposite = new boolean[n];
isComposite[0] = isComposite[1] = true;
for (int i = 2; i < Math.sqrt(n); ++i) {
    if (!isComposite[i]) {
        for (int j = i * i; j < n; j *= i) {
            isComposite[j] = true;
        }
    }
}

This is the classical implementation of the sieve. The resulting array isComposite will hold a value of false for prime values.

Now, observe that the first time you ever see a prime, you remove all of its multiples from contention. We can therefore store a separate list containing just these primes. (We also have to loop over the back half of the array to get any primes >= sqrt(n).)

List<Integer> primes = new ArrayList<Integer>();

boolean[] isComposite = new boolean[n];
isComposite[0] = isComposite[1] = true;
for (int i = 2; i < Math.sqrt(n); ++i) {
    if (!isComposite[i]) {
        primes.add(i);
        for (int j = i * i; j < n; j *= i) {
            isComposite[j] = true;
        }
    }
}
for (int i = (int)Math.sqrt(n); i < n; ++i) {
    if (!isComposite[i]) {
        primes.add(i);
    }
}

Finally, we can determine the range of primes we want. To do this, perform a binary search on primes to find the lower and upper bound. Then, select a random element from the list.

You may wish to save this list of primes, so that it only need be computed once. In particular, observe that the sieve of Eratosthenes can be "paused" and "resumed" in computation, so that the results of previous computations may be used in future computation. I leave this as an exercise to the reader.

\$\endgroup\$
4
\$\begingroup\$

I'll concentrate on the syntactical issues in this review since the others have already commented on the other parts of the code.

import acm.program.*;
import acm.util.RandomGenerator;

public class exercise4 extends Program {
public int nextPrime(int n){                                          //sieve of Eratosthenes
        final RandomGenerator rgen = RandomGenerator.getInstance();
        boolean[] array = new boolean[n];

Your code is difficult to read for an experienced Java programmer because you violate all kinds of conventions:

  • Class names start with an uppercase letter, yours (exercise4) doesn't.
  • After every opening {, the code is written one more level to the right. So the line that declares nextPrime should be more to the right. Ideally you let your IDE format the code for you. For Eclipse, press Ctrl+Shift+F, for IntelliJ press Ctrl+Alt+L, for Netbeans Alt+Shift+F.
  • rgen is a final variable, but array isn't. That's inconsistent. Either both or none should be final.

Continuing:

        for (int i=2; i<n;i++) {

You should leave some space around the operators, so write for (int i = 2; i < n; i++) {.

            array[i]=true;
        }
        int i=2;
        while (i<Math.sqrt(n)) {
            if (array[i]==true) {

You can leave out the == true.

                int m=i*i;
                int j=0;
                while (m+j*i<n) {

You should never call this code with an n that is close to Integer.MAX_VALUE. Otherwise the expression m + j * i will overflow and become negative, and something negative is surely smaller than a large n.

                    array[m+j*i]=false;
                    j++;
                };
            };
            i++;
        };
        int random;
        do {
            random=rgen.nextInt(n);
        } while(array[random]==false);
        return random;
    }
    public void run(){
        //long start = System.currentTimeMillis(); 
        println(nextPrime(2_000_000));
        //long elapsedTimeMillis = System.currentTimeMillis()-start;
        //float elapsedTimeSec = elapsedTimeMillis/1000F;
        //println("Completed in: "+elapsedTimeSec+" seconds.");
    }
}
\$\endgroup\$
3
\$\begingroup\$

Your code wouldn't compile because you give nextPrime two arguments but it expects only one. Also, I think your parameter names should be a little clearer than n. You say it's in a range, so let's say it in the code :

public int nextPrime(int start, int end)

I won't concentrate on the sieve itself, but your code could be drastically improved in performance with some caching.

If I call :

nextPrime(20_000, 2_000_000);
nextPrime(50_000, 1_000_000);

You compute the sieve twice while the result could be cached. Compute the prime numbers at most once, and you'll save some processing time.

You could potentially keep the prime numbers in a binary tree, which would make the search a little faster than a simple list. When you ask for a specific range, check in your tree if this range already exists, if so, pick a random prime number in this range. If there's a part of the range that already exists, compute the rest of the range and add it to your tree. If the range doesn't exist at all, compute it all and add it to the tree.

If you use this generator a lot, you'll realize the performance will be much better.

Also, maybe create a class to hold all this information.

\$\endgroup\$
  • \$\begingroup\$ I thought too that i should be more specific about the n parameter but i also thought it could be obvious its purpose.About the two args i give to the method, you are right, i did it by mistake and i edited my original post. Your ideas is good but i can only understand this with the cache(i'm not thatexperienced yet to work with binary trees). Also i should be more specific about the following: i am not trying to improve sieve of Eratosthenes. I'm trying to think of a completely new implemetation propably, that surerly has no arrays and would be even faster than my current implementation. \$\endgroup\$ – Κωνσταντίνος Κορναράκης Jan 15 '18 at 21:46
  • 2
    \$\begingroup\$ @ΚωνσταντίνοςΚορναράκης the Sieve is a pretty efficient way to generate primes, I doubt you'll find some much better methods for your use case. You can search the web for other ways to generate primes still.. I really think your best shot at performance is what I said :) \$\endgroup\$ – IEatBagels Jan 15 '18 at 22:12
2
\$\begingroup\$

The one performance thing I see is that you can calculate the value of

Math.sqrt(n)

outside of the loop so that it doesn't have to be calculated each time.

double squareRoot=Math.sqrt(n)
while (i<Math.sqrt(n)) {

I am not familiar with the sieve of Eratosthenes but if you could find a way to store only the primes and return a random one from that, it should speed your code up.

\$\endgroup\$
  • \$\begingroup\$ I agree about calling Math.sqrt() outside the loop. But, i am not sure of your second suggestion, i didn't really understand because i need to pick a random number. \$\endgroup\$ – Κωνσταντίνος Κορναράκης Jan 15 '18 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.