Improved RandomGenerator with nextPrime() method 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&lt;n;i++) {
            array[i]=true;
        }
        int i=2;
        while (i&lt;Math.sqrt(n)) {
            if (array[i]==true) {
                int m=i*i;
                int j=0;
                while (m+j*i&lt;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.");
    }
}
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&lt;n;i++) {


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

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


You can leave out the == true.

                int m=i*i;
                int j=0;
                while (m+j*i&lt;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.");
    }
}